프로그래밍 diary

11660번 - 구간 합 구하기 5 https://www.acmicpc.net/problem/11660 11660번: 구간 합 구하기 5 첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 www.acmicpc.net 문제 접근은 쉽다. 값을 입력 받아 배열에 저장하고 시작점부터 끝점까지의 누적 합을 구하면 된다. 시간초과될 것을 알면서도 일단은 이중 for문을 사용하여 코드를 작성하고 제출해봤다. 좌표값을 입력 받을 때 사용하는 이중 for문은 필요한 과정이라고 생각을 했고, 누적 합을 구하는 과정에서 사용되는 이중 for문을 없애..

11057번 - 오르막 수 https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 점화식: dp[i][j] = dp[i - 1][j] + dp[i][j - 1] 마지막 자리수의 값을 기준으로 문제를 풀었다. 3자리 숫자의 경우 003, 013, 113, 023, 123, 223, 033, 133, 233, 333 이렇게 총 10가지의 오르막 수로 구성된다. 바로 위의 풀이에서 볼 수 있듯이 마지막 수를 제외한 나머지..

10844번 - 쉬운 계단 수 https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N = 1 1, 2, 3, 4, 5, 6, 7, 8, 9 N = 2 10, 12, 21, 23, 32, 34, 43, 45, 54, 56, 65, 67, 76, 78, 87, 89, 98 N = 3 101, 121, 123, 210, 212, 232, 234, 321, 323, 343, 345, 454, 456, 432, 434, 543, 545, 565, 567, 654, 656, 676, 678, 765, 767, 787, 789, 876, 878, 898, 987, 989 처..

1912번 - 연속합 https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 완성된 dp 배열에서 최댓값을 출력하면 문제에서 찾는 답이 된다. 점화식: dp[i] = dp[i] + dp[i-1], dp[i] = arr[i] 더보기 #include using namespace std; int n; int dp[100001] = { 0, }; int arr[100001] = { 0, }; int main() { cin >> n; for (int i = 1; i > ..

1699번 - 제곱수의 합 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net 점화식: dp[i] = dp[j * j] + dp[i - j * j] = 1 + dp[i - j * j] #include #include using namespace std; int N; int dp[100001] = { 0, }; int solution(int n) { //제곱근이 맞으면 0, 아니면 1 long long re; ..