곽로그

문제 www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static long[] d; public static long MOD = 1000000009; public static void main(String[] args) thr..

문제 www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 0부터 n개의 수 k개를 더해서 n을 만든다고 할때 맨 마지막에 더하는 수를 생각해보자. 그 마지막 수에 올 수 있는 수는 0~ n이다. 마지막 수 앞에 오는 수는 0~ (n-마지막수) 중 k-1 개를 더해서 만든 수다. 따라서 f(n,k) 를 0부터 n까지의 수 k개를 더해서 n을 만들 수 있는 경우의 수라고 하면 f(n,k) = f(n-m,k-1) (0

문제 [https://www.acmicpc.net/problem/14002] 풀이 소스 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.StringTokenizer; public class Main { public static int N; public static int[] numArray; public static int[] longestArr..

문제 https://www.acmicpc.net/problem/10844 풀이 f(n) 을 길이가 n인 계단 수의 갯수라고 하자 그런다음 f(n-1), 즉 길이가 n-1인 계단 수의 갯수와 길이가 n인 계단 수의 갯수가 어떤 관계인지를 생각하자. f(n)은 길이가 n-1 인 계단수의 끝자리에 무엇이 오는 지에 따라 갯수가 정해진다. n-1계단 수의 끝자리가 m이면 n계단 수의 끝자리에 올 수 있는 수는 m-1 또는 m+1 이다. d[n][m]을 길이가 n인 계단 수중에 끝자리가 m인 것의 갯수라고 하면 d[n][m] = d[n-1][m-1] + d[n-1][m+1]이다. 이때 m=1인 경우와 m=9인경우는 따로 처리해주면 된다. 주의사항 d[n][m] = d[n-1][m-1] + d[n-1][m+1]을 ..

문제 www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 처음엔 풀지 못했다가 강의를 듣고 힌트를 얻었다. 이 문제의 핵심은 "같은 수를 두번 이상 연속해서 사용하면 안된다"이다. 이게 어려웠다. f(n)을 1,2,3의 합을 이용해서 나타내는 방법 중 같은 수를 두번이상 사용하지 않은 경우의 수라고 정의해보자. 그런 뒤 f(n)과 f(n-1), f(n-2), f(n-3)과의 관계를 생각해보자 우선 f(n) 과 f(n-1)의 관계를 보면, f(n-1) 은 끝자리가 1, 2, 3 중 하나로 끝나게 된다. 이때 ..

문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 풀이 1. 단순재귀 - 입력의 최대가 11이므로 memoization이 없어도 시간초과가 나지않는다. [백준 9095, Java] 1,2,3 더하기 문제 www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 코드 import java.io.BufferedReader; import java.io... alwaysbemoon.tistory.com 2. 점화식 - 이..

문제 www.acmicpc.net/problem/11727 11727번: 2×n 타일링 2 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다. www.acmicpc.net 풀이 - 2 X n 타일링 문제와 비슷하다 - F(N) 을 구할때 F(N-1) + F(N-2)에서 F(N-2) 즉 2*(N-2)의 직사각형을 구하는 방법은 마지막에 2*2타일을 채우는 방법, 1*2 타일로 채우는 방법 2가지가 있으므로 F(N) = F(N-1) + F(N-2) *2가 된다 [백준 11726, Java] 2 Xn 타일링 문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 ..

문제 www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 접근 1.처음 접근 방법 (1 X 2 타일의 갯수를 기준으로) - 1 X 2 타일을 0개 쓴다. 2개 쓴다, 4개 쓴다를 기준으로 잡았다. 예를 들어 N = 5라고 했을 때 1 X 2 타일을 0 개쓰면 2 X1 타일로만 채우게 되므로 경우의 수는 1이다. 1 X 2 타일을 1개를 쓴다고 했을 때, 1 X 2 타일 위 또는 아래에는 반드시 1 X 2 타일이 올 수 밖에 없으므로 1X2 타일은 짝수개를 쓰게 된다. 따라서 1 X ..