Algorithm & Data Structure/백준

[JAVA] 백준 2293번 : 동전 1

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 - n가지 종류의 동전이 주어지고, 각각의 동전이 나타내는 가치는 다를 때, 그 가치의 합이 k원이 되도록 하는 그 경우의 수를 구하는 프로그램. - 각각의 동전은 몇 개라도 사용가능 - 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우로 침. 입력 - 첫째 줄에 n, k가 주어짐. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) - 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. (100,000보다 작거나 같은 자연수) 출력 첫째 줄에 경..

[JAVA] 백준 9461번 : 파도반 수열

9461번: 파도반 수열 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 � www.acmicpc.net 문제 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다. 파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다. N이 주어졌을 때, P(N)을 구하는 프로그..

[JAVA] 백준 11726번 : 2Xn 타일링

11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 - 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력. 풀이 처음부터 노가다로 구해보니까 점화식이 나왔다. DP[N] = DP[N-1]+DP[N-2] 임을 확인할 수 있다.. public class bj11726 { public static void main(String[] args) { //..

[JAVA] 백준 2225번 : 합분해

2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 - 0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램 - 덧셈의 순서가 바뀐 경우 다른 경우로 셈(1+2와 2+1은 다른경우) - 한 개의 수를 여러번 쓸 수 있다. 입력 첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200) 출력 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력. 풀이 만약 입력에 5, 3가 주어졌다고 가정했을 때, 생각할 수 있는 경우의 수는 아래와 같다. 5 = 0 (2번 더해서 0이 되는 경우)+ 5 5 = 1 (2번 더해서 1이 되는 경우)+ 4 5 = 2 (2번 더해서 2이 되는 경우)+..