PS
BOJ 2011 암호코드
boj 2011 암호코드 - 문제 링크 https://www.acmicpc.net/problem/2011 - 문제 해설 DP를 이용하여 간단히 풀 수 있는 문제이다. D[i]가 주어진 암호의 i번째까지에서 해석할 수 있는 가짓수라고 하자. 끝 두자리의 숫자가 10 ~ 26 범위이면 한자리 숫자 2개가 될 수도 있고 두자리 숫자 1개가 될 수도 있다는 점을 생각하면 문제를 쉽게 해결할 수 있다. 생각해볼 사항들이 무엇이 있는지 살펴보자. 암호의 처음 숫자가 0일 시에는 0을 출력한다. 맨 끝 한 자리가 0인 경우는 맨 끝 두 자리가 10, 20인 경우를 제외하고는 암호가 성립할 수 없다. 예를 들면 맨 끝 두 자리가 00, 30, 40 ... 90 같은 경우는 대응되는 알파벳이 없기에 암호가 성립되지 못한..
BOJ 2225 합분해
boj 2225 합분해 - 문제 링크 https://www.acmicpc.net/problem/2225 - 문제 해설 테이블 D[i][j]를 n이 i이고 k가 j일 때의 경우의 수라고 정의한다. 경우의 수를 어떻게 나눌지 잘 떠오르지 않아서 일단 n과 k에 따른 경우의 수를 작은 수부터 나열해보았다. 표로 나열해보면서 점화식을 유추해보자. 예를 들어 D[3][3]을 구한다고 해보자. 3을 3가지 수의 합으로 나타내는 경우는 0부터 3까지의 수를 2가지 수의 합으로 나타낸 것에다가 3이 되기위해 필요한 수를 더하면 된다. 0을 2가지 수의 합으로 나타낸 경우 : (0 + 0) 1을 2가지 수의 합으로 나타낸 경우 : (0 + 1), (1 + 0) 2를 2가지 수의 합으로 나타낸 경우 : (0 + 2), (..
BOJ 9461 파도반 수열
boj 9461 파도반 수열 - 문제 링크 https://www.acmicpc.net/problem/9461 - 문제 해설 첫 5항만 제외하고 나머지 항들은 전부 규칙을 따라 증가하는 형태이다. P(1)부터 P(10)을 보면 1, 1, 1, 2, 2, 3, 4, 5, 7, 9 이다. 길이가 3인 삼각형은 1과 2를 더해서 생기고, 길이가 4인 삼각형은 1과 3을 더해서, 길이가 5인 삼각형은 1과 4를 더해서 생긴다. D[i] = D[i-1] + D[i-5] 의 규칙을 따라 증가한다. 그러므로 1~5항을 따로 초기화해주고 나머지는 위 점화식을 따라 구해준다. - 코드 보기 #include using namespace std; int t; int n; long long P[105]; int main(voi..
BOJ 2133 타일 채우기
boj 2133 타일 채우기 n이 홀수일 때, 타일을 전부 채울 수 있는 방법은 없다. 그러므로 n이 짝수일 때만 살펴보면 된다. 테이블 D[i]를 n이 i일 때, 타일을 전부 채울 수 있는 방법 수라고 정의하자. 타일이 2칸일 때 채울 수 있는 방법의 수가 3가지인 것은 쉽게 알 수 있다. 그리고 힌트를 보면 4칸의 경우 2칸인 경우를 이용하지 않고 채우는 방법이 2가지가 있다는 것을 알 수 있다. 이 사실만으로 간단하게 점화식을 D[i] = D[i-2]x3 + D[i-4]x2 라고 하면 틀린다. 위의 사진을 보면, 타일이 2칸씩 늘어날 때마다 채우는 방식 2가지가 추가된다. 이를 바탕으로 점화식을 구현해보자. D[i] = D[i-2]x3 + D[i-4]x2 + D[i-6]x2 + ... + D[0]x..
BOJ 1699 제곱수의 합
boj 1699 제곱수의 합 수가 주어지면 그 수를 제곱수들의 합으로 표현할 때, 최소의 항 갯수를 구하는 문제이다. 모든 수는 1의 합으로 표현할 수 있기에 최대의 항 갯수는 입력된 수의 크기와 동일하다. 그러므로, 테이블 D[i]를 i를 제곱수의 합으로 표현할 때의 최소의 항 갯수라고 정의하면, D[i] = i 라고 초기 값을 지정해줄 수 있다. 최소의 항 갯수를 구하는 방법은 간단하다. i에서 i를 넘지 않는 제곱수를 빼면서 최소 항의 갯수를 변경해주는 것이다. 이를 점화식으로 나타내보자. D[i] = min(D[i], D[i - 제곱수]+1) 이때, +1을 해주는 이유는 제곱수에 해당하는 항 갯수를 더해주는 것이다. #include #include using namespace std; int n;..