https://www.acmicpc.net/problem/2637 예제785 1 25 2 27 5 26 5 26 3 36 4 47 6 37 4 5출력 : 1 162 163 94 17하나의 완제품을 완성하는데 필요한 기본 부품의 수를 구하는 문제이다. 어떤 부품이 기본 부품인지를 구하고, 중간 부품을 기본 부품으로 치환하는 방식으로 풀이를 떠올렸다. dp를 사용한 방식인데 2차원 배열로 dp 배열을 선언해서 dp [i][j]를 i번 부품을 만드는데 필요한 j 부품의 수 (j는 기본 부품)로 생각하고 구현했다. 해당 풀이의 점화식은 다음과 같다.i번 부품에 대해(i는 중간 부품) dp[i] = dp [next.first] * next.second. next는 i번 부품을 만드는데 필요한 부품이다. 백준에서 ..

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 조건제한이 걸린 경로를 찾는 문제이다. 가장 먼저 떠올린 풀이는 dp [i][j]를 (i, j)까지 도달할 수 있는 경우의 수로 두고 네 방향 모두에서 (i, j)로 도달할 수 있으므로 4방향을 순차적으로 채우는 방법이었다. 이 방법은 아래와 같은 케이스를 잡아내지 못했다. 다음에 떠올린 방법은 DFS였다. DFS에서 백트래킹 느낌으로 메모이제이션을 떠올릴 수 있었다. 어떤 점 (i, j)에서 더 이상 갈 수 있는 곳이 없으면 (i, j)에 도달하면 바로 종료하는 방..

2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net 문제를 읽었을 때 바로 느껴지는 점은 어째서 암호코드 가짓수를 구하는 거야...? 였다. 농담이고 전에 푼 다른 DP 문제가 떠올랐다. [BOJ] C++ 2193: 이친수 - DP 테이블링 연습하기 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으 jun-n.tistory.com 이 문제랑 굉장히 비슷한 과정으로 테이..

9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 예제를 좀 손으로 써보면 바로 규칙이 보인다. 완벽하게라는 말에 빠져들면 좀 돌아갈 수 있는데 그냥 간단하게 우선권이 상근이한테 있고, 두 명 모두 최대한 자기가 이길 수 있는 수를 둔다는 뜻이다. 돌이 5개 이하일 때는 바로 답이 보이므로 돌 6개부터 보자. 상근이가 처음에 돌을 1개 가져가면 창영이는 5개에 대해 게임을 시작한다. 상근이가 3개를 가져가면 창영이는 3개로 시작한다. 5개로 시작하는 경우 시작하는 사람이 이긴다. 3개도 마찬가지다. 규칙이 좀 보일 텐데 바로 일반화시켜 보자. k개로 상근이가 게임을 시작한다고 생각해 보자. 상근이가 1개 가져가면 창영이는 k-1개로..

10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 예제 7 1 2 1 3 1 2 1 4 1 3 2 5 3 3 5 7 ans : 1 0 1 1 문제를 보면 수는 2000개밖에 안되는데, 질문이 최대 백만 개다. 또 수의 최댓값이 백만이다. 질문의 수가 많고 시간이 0.5초밖에 안 돼서 질문이 들어오면 상수시간 안에 답해야 한다고 생각하고 풀이를 떠올려 봤다. 상수시간 안에 답하려면 브루트포스를 사용하면 될 것 같아서 이차원 테이블로 dp [i][j] = number [i] ~ number [j]까지 펠린드롬인지 저장해 두는 방향으로 가닥을 잡았다. 그런..

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 가장 먼저 떠오른 풀이는 백트래킹으로 모든 점을 탐색하면서 해당 점에서 한 변의 길이가 k인 정사각형을 만들 수 있는지 체크하는 풀이였다. 시간복잡도가 O(n^2 * m^2)이라 시간초과가 뜰 것 같아서 일단 패스했다. 시간초과를 생각해 보면 O(nm)으로 풀어야 한다. 즉, 한 번의 테이블 순회로 정사각형의 크기를 알아낼 수 있어야 한다는 뜻이다. 굉장히 규칙을 찾기가 힘들어서 테이블 순회는 어차피 열이나 행을 한줄씩 쭉 읽는 방식으로 작동하기에 한 번 손으로 순회하면서 어떻게 하면 한 번에 정사각형을 찾을 수 있을지 생각해 봤다..