개발여행

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 처음 이 문제를 봤을 때 수의 거대함(?)을 간과하고 몇가지 예로 점화식을 만드려 했다가 낭패를 볼 뻔했다.. 그냥 간단히 표를 이용해 나타내면 규칙이 쉽게 보인다. K = 1 일때는 N 값에 상관없이 dp[N][1] = 1 이고 N = 1 일 때는 dp[1][K] = K이며 그 외에는 모두 표에서 왼쪽 값과 위쪽 값을 더한 dp[N][K] = dp[N-1][K] + dp[N][K-1] 임을 알 수 있다. N, K = list(map(int, input().split())) dp = [1] * N for _ in range..

https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 점화식 작성에 앞서 그림으로 문제를 이해하는게 편할것 같아서 그림을 그려보았다. 우선 n이 홀 수 일 때는 개수가 맞지않아 경우의 수는 모두 0이므로 짝 수일 때만 생각하면 된다. n = 2 일 때 세가지 경우가 생긴다 n = 4 일 때는 그림과 같이 양쪽에 세로 타일 하나씩 사용하고 나머지는 가로 타일만 사용한 모양 두가지와, n=2 일 때 모양을 두번 조합한 경우가 생긴다. 이 때 가능한 총 경우의 수는 2 + 3 * 3 = 11 이다. 경우의 수 조합을 위해 두 부분으로 나누어 계산을 했는데 왼쪽은 d..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net N이 주어졌을 때 제곱수를 가장 적게 이용해 N을 만드는 문제이다. 우선 N을 구성하는데 사용할 수 있는 제곱수 중 가장 큰수를 m2 이라한다. m = int(√ N) N = 12 일 때 가능한 경우 -> m = int(√ 12) = 3 이므로 i = 1, 2, 3 12 = 32 + 12 + 12 + 12 = 32 + 3 12 = 22 + 22 + 22 = ..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net 우선, A의 길이 만큼 0으로 채워진 dp 리스트를 생성한다. dp는 해당 인덱스까지 수열을 만들 경우 가장 길이가 길 때의 길이를 나타낸다. i=0 부터 n 까지 A[i] 보다 빠른 숫자들 중 A[i]보다 작고 가장 길이가 긴 경우를 구하고 그 길이에 1을 더해주면 된다. import sys input = sys.st..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net N(길이)이 1일 때는 일의 자리 숫자가 무엇이든 0을 제외한 모든 숫자에 1가지 경우의 수가 생긴다. N이 2라면 십의 자리 숫자에 따라 일의 자리 숫자가 달라지는데 우선 십의 자리에는 0이 올 수 없다. 일의 자리가 0이 되는 경우는 십의 자리가 1일 때만(10) 가능하다. 십의 자리에는 0이 올 수 없으므로 일의 자리가 1인 경우도 십의자리가 2일때만(21) 가능하다. 또한 일의 자리가 9인 경우는 십의 자리가 8일 때만(89) 가능하다. 이 외에는 모두 두가지 경우가 생긴다. 자릿수가 커지더라도 최종적으..