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,..