코딩스토리

https://www.acmicpc.net/problem/14289 14289번: 본대 산책 3 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 결국 정보대에서 정보대까지 d번만에 가는 경우의 수를 구해야 하는 문제였다. 이를 일반화해보면 "A 노드에서 B 노드까지 d번만에 가는 경우의 수"를 구해야 한다. 이 부분에 dp 스럽게 생각해보면 "A노드에서 B와 연결된 모든 노드까지 d-1번 만에 도착하는 경우의 수들의 합"과 같다. 즉 식으로 나타내면 다음과 같다. dp [i][j][k] = i 노드에서 j 노드까지 k번 만에 도착하는 경우의 수라고 가정해보자. 그렇다면 dp[i][j][k]는 아래와 같이 구할 수 있다. for(int a = 1; a i..

https://www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 본격적인 행렬 제곱 DP를 사용한 문제이다. 피보나치 수를 구하는 문제는 다이나믹 프로그래밍의 전형적인 문제 유형이다. 대부분 DP를 시작하는 사람들은 피보나치 수를 처음 접하면서 시작한다. 이 문제 역시 피보나치 수를 구하는 문제이다. 다른 점은 n 제한 하나이다. 이 문제의 n제한은 "1,000,000,000,000,000,000"이다. 이번에도 이 숫자가 내 통장잔고였으면.. 하지만 이번 건 스케일이 좀 남다르다. 내 통장잔고의 문제가 아니라 몇 년치 국가 예산보다 크지 ..

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 행렬 제곱 DP를 공부하기 위해 먼저 이 문제를 풀어보았다. 주어진 조건 중 "1 ≤ B ≤ 100,000,000,000"을 보고 저게 내 통장 잔고였음 좋겠다... 뻘 생각 한번 해주고 시간 복잡도는 O(logN)으로 구해야겠다 싶었다. 내가 문제를 보고 생각했던 logN 풀이는 반드시 (A^2)*(A^2) = A^4를 만족해야 했다. 나는 행렬을 고등학교때 배우고 온 세대가 아니기 때문에(나름 신생아^^) ..

www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 이분 탐색으로 쉽게 해결할 수 있었던 문제이다. 문제 태그에는 수학, 투 포인터가 적혀 있는데 나는 문제를 보고 이분 탐색으로 충분히 풀릴 것 같아서 제출해봤는데.. 틀렸습니다.. 잉? 하고 문제를 다시 보니 가능한 몸무게가 없을 때 -1을 출력하는 것을 까먹어버렸다ㅎㅎ 저 조건을 다시 붙여서 바로 제출하니 맞았습니다를 받을 수 있었다. 풀이 과정 일단 G의 값이 100000 보다 작은 자연수라는 조건이 가장 큰 힌트..

www.acmicpc.net/problem/2602 2602번: 돌다리 건너기 첫째 줄에는 마법의 두루마리에 적힌 문자열(R, I, N, G, S 로만 구성된)이 주어진다. 이 문자열의 길이는 최소 1, 최대 20 이다. 그 다음 줄에는 각각 와 를 나타내는 www.acmicpc.net KOALA의 이번 주 모의테스트 문제였다. 누가 봐도 DP 문제였다. 처음에 문제를 제대로 안 읽고 풀다가 시간을 많이 날렸다. 돌다리의 길이가 최대 100인데 10으로 보고 풀다가.. 내 시간ㅠㅠ 핵심은 반드시 한 번씩 마법의 두루마리에 적힌 문자열을 모두 밟아야 한다는 것이다. dp 문제의 핵심은 당연히 dp를 어떻게 정의하냐이다. 나는 dp[ i ][ j ][ k ]를 아래와 같이 정의했다. 마법의 두루마리에 적힌 ..