조준화의 오류정정

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)으로 풀어야 한다. 즉, 한 번의 테이블 순회로 정사각형의 크기를 알아낼 수 있어야 한다는 뜻이다. 굉장히 규칙을 찾기가 힘들어서 테이블 순회는 어차피 열이나 행을 한줄씩 쭉 읽는 방식으로 작동하기에 한 번 손으로 순회하면서 어떻게 하면 한 번에 정사각형을 찾을 수 있을지 생각해 봤다..

https://www.acmicpc.net/problem/9084 9084번: 동전 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 www.acmicpc.net 예제 3 2 1 2 1000 3 1 5 10 100 2 5 7 22 ans : 501 121 1 주어진 n개의 동전으로 숫자 m을 만드는 방법의 수를 구하는 문제이다. 가장 먼저 떠오르는 방법은 역시 완전탐색이다. 최대 20개의 동전을 종류별로 다 더해주면서 계산하면 답이 나올 것 같긴 한데 굉장히 오래 걸리고 중복이 많이 발생할 것 같았다. 따라서 완전탐색은 안된다 생각하고 1,..

10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제를 분석해 보면 자릿수별로 테이블링을 해서 전의 항을 사용할 수 있을 것 같다. 일단 dp로 잡고 테이블링도 dp [k]를 k자릿수에서의 계단 수라고 설정한 뒤 점화식을 구해봤다. 분명 아래 사진처럼 k-1 자릿수를 k 자릿수 구할 때 사용할 수 있긴 한데 특이 케이스를 고려해줘야 했다. k의 값에 따라서 특수 케이스의 계단수가 달라지는 건 확실한데 그 규칙을 정확하게 파악하기 힘들어서 간단하게 다차원 배열을 사용했다. dp [i][j]를 i자릿수에 대해 j로 시작하는 계단수로 설정하니 점화식이 보였다. j==0이면 dp [i][0] = dp [i-1][1] j==9면 dp..

15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이전에 백트래킹으로 푼 문제와 똑같은데 입력의 크기가 많이 큰 문제이다. 이 정도 크기면 O(N^2)은 당연히 안되고 O(N)이나 O(N log N)으로 풀어야 한다. 풀이를 떠올리기 굉장히 힘들었는데, 그리디 하게 풀면 당연히 안되고 dp로 풀자니 테이블링이 쉽지 않았다. 테이블을 앞에서부터 탐색하면서 점화식을 찾으려 했는데 도저히 답이 나오지 않아서 정답을 살짝 참고했다. 바킹독님의 풀이에는 테이블링을 뒤에서부터 시작하면서 dp[..

2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net DP문제인데, DP문제의 가장 중요한 점은 문제를 보고 DP를 떠올릴 수 있어야 하고 테이블링을 할 수 있어야 한다. 가장 먼저 떠오른 풀이는 백트래킹이다. n자리를 모두 체크해보고 이친 수인지 판단하는 방법인데, 2^n의 데이터를 검사해야 하므로 바로 패스했다. 또 바로 떠오르는 풀이가 없으니 일단 n=1부터 n을 증가시키면서 규칙을 찾아보았다. 다행히 n=3부터 n=1에서 구했던 부분을 써먹을 수 있었다. n을 계속 늘려가면서 6 정도까지 관찰해 ..