DP

[11048] 이동하기

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 �� www.acmicpc.net 🔎 해결 방법 (1, 1)에서부터 (n, m)까지 가면서 오른쪽, 대각선, 아래쪽 중 가장 큰 값을 더해나가면 되지 않을까? 그럼 dp가 필요없는데? 라고 생각했지만 이 문제를 dp로 풀어야 하는 이유가 있다. 만약의 미로가 위와 같이 주어졌다면, 현재 내 위치에서 갈 수 있는 칸 중 가장 최댓값만 취해서 이동한다면 위와 같이 되고, 이것은 dp가 아니라 그리디 알고리즘이라고 ..

[14501] 퇴사(C++)

🍃 문제 바로가기 🔎 해결 방법 처음에는 앞에서부터 계산을 하려고 했었다. 예를 들어, dp[n] 을 n일까지 상담을 했을 때 얻을 수 있는 최대 이익이라고 한다면 가능한 모든 경우를 조합해서 그 중 max 값을 찾아서 dp에 저장하려고 했는데 이렇게 하다보니 예외 처리 해줘야 할 것이 너무 많아서 결국 구글링의 도움을 받았다. 첫째날부터 계산을 해도 풀 수 있긴 하지만, 마지막 날 부터 계산을 한다면 코드도 간결하고 훨씬 더 간단하게 답을 도출할 수 있다! 만약 위와 같은 표가 주어졌다면, 1. dp[7] 7 + t[7] = 9 > 8 이므로 7일에 있는 상담은 할 수 없다. 따라서 dp[7] = dp[8] = 0 (dp[n + 1] = 0으로 사전에 초기화 해줘야 함) 2. dp[6] 6 + t[6]..

[11052] 카드 구매하기

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 🔎 해결 방법 예를 들어 민규가 구매하고자 하는 카드의 개수가 4개라면, 가능한 조합은 4 / 3 + 1 / 2 + 2 / 2 + 1 + 1 / 1 + 1 + 1 + 1 이므로 자연수의 분할로 접근하면 되는 줄 알았다. 그러면 각 경우는 위와 같이 계산하면 되는데 2 +2 가 문제였다. dp를 생각하지 못하고 2 + 2를 계속 p[2] + p[2]라고 계산하는 바람에 점화식을 세울 수 없었다. 하지만! ..

[1003] 피보나치 함수(C++)

https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 🔎 해결 방법 fibo(n) = fibo(n-1) + fibo(n-2) 인 것과 마찬가지로 0과 1이 출력되는 횟수도 이전의 두 개를 더해주면 된다. 즉, 점화식은 1. dp[n][0] = dp[n-1][0] + dp[n-2][0] 2. dp[n][1] = dp[n-1][1] + dp[n-2][1] 이렇게 두 가지를 사용하면 된다. 💡내 코드(C++) // [1003] 피보나치 함수 // https://www.acmicpc.net/problem/1003 #include using namespa..

[10844] 쉬운 계단 수

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 🔎 해결 방법 dp[1] = 9 dp[2] = 17 dp[3] = 32 dp[4] = 61 까지 찾고 점화식은 dp[i] = dp[i-1] * 2 - 1 이네! 하고 제출했는데 자꾸 틀렸다고 떠서 질문들을 찾아보니....전부 dp를 2차원으로 선언했길래 굳이 2차원까지 써야 돼? 나는 1차원으로 해결하겠어...라며....1차원으로 하다가... 결국 2차원으로 선언했다.ㅎㅎ 이건 가지치기로 나타내서 보면 이해하기가 쉬운데, 아래의 그림을 보자. 우선 이 문제에서 dp는 dp[길이][최고 자리 수] 로 정의했다. ..

분할 정복(Divide and Conquer)

[2225] 합분해(C++)

문제 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 해결 방법 dp[i][j] = 0 ~ i까지의 정수 j개를 더해서 그 합이 i가 되는 경우의 수 내 코드(C++) // [2225] 합분해 // https://www.acmicpc.net/problem/2225 // dp // dp[i][j] = 0 ~ i까지의 정수 j개를 더해서 그 합이 i가 되는 경우의 수 #include using namespace std; int main(void) { long dp[201][201]; int n, k; cin >> n >> k; for (int i = 0; i < 201; i++) { dp[0][i] = 0; dp[1][i] = i; dp[..

[2193] 이친수

문제 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 내 코드(C) #include #define MAX 1000000 int main(void) { int n; long dp[MAX]; dp[0]=0, dp[1] = 1, dp[2] = 1; scanf..