* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 문) 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오. 덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다. 입) 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다. 출) 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. 풀이 1. 테이블 정의 dp[k][n] = k개의 ..
* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 풀이 평소에는 Bottom-Up(for문) 방식을 택하여 많이 풀었는데, 오늘은 Top-Down(재귀) 방식으로 풀었다. 1. 테이블 정의 : P(N) = 마지막 정삼각형의 변의 길이 2. 점화식 : d[i] = d[i-1] + d[i-5]; 나선형으로 도는 삼각형의 값을 하나하나 나열하면서 규칙성을 찾았다. cf. 궁금해서 찾아본 다른 풀이 1~3까지의 값만 할당해주고 나머지는 d[i] = d[i-2] + d[i-3] 의 점화식 적용. 필자는 ..
문) 수 N개 A1, A2, ..., AN이 주어진다. A를 오름차순 정렬했을 때, 앞에서부터 K번째 있는 수를 구하는 프로그램을 작성하시오. 입) 첫째 줄에 N(1 ≤ N ≤ 5,000,000)과 K (1 ≤ K ≤ N)이 주어진다. 둘째에는 A1, A2, ..., AN이 주어진다. (-109 ≤ Ai ≤ 109) 출) A를 정렬했을 때, 앞에서부터 K번째 있는 수를 출력한다. 풀이 & 코드 솔직히 푼 거 후회했다. 7전 1승의 너덜너덜한 승리를 쥐고, 연구과제로 남기려고 작성한다. 1. 라이브러리 활용 1차 시도 : 시간 초과 ❌ 제한 시간 2초, 찾아보니 자바는 (제한시간)*2 +1 초 준다고 한다. 그런데도 초과. import java.io.*; import java.util.*; public c..
* 공부 목표 DP - 1463, 11726, 11727, 9095, 10844, 11057, 2193, 9465, 2156, 11053, 11055, 11722, 11054, 1912, 2579, 1699, 2133, 9461, 2225, 2011, 11052 문) 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입) 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출) 첫째 줄에 경우의 수를 출력한다. 풀이 1. 테이블 정의 : dp[i] = 경우의 수 2. 점화식 dp[i] = dp[i-2] * dp[2] +{ dp[i-4]*2 + dp[i-6]*2 + ... + dp[0] *2 }; 3xn 타일이기 때문에, 짝수만 가능하다. 위의 점화식은 쉽게 말하면, 직전 값 *..
