다이나믹 프로그래밍

[BOJ/JAVA] 1958번: LCS 3

1958번: LCS 3https://www.acmicpc.net/problem/1958키워드LCS(Longest Common Subsequence)문자열 3개의 LCS를 구하는 프로그램구현LCS가 무엇인가?[BOJ/JAVA] 5582번: 공통 부분 문자열5582번: 공통 부분 문자열 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 키워드 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 구현 대표적인 LCS문제. 두 문자열 중 공통 부분 문..

[BOJ/JAVA] 11060번: 점프 점프

11060번: 점프 점프https://www.acmicpc.net/problem/11060키워드i번째 칸에 쓰여 있는 수를 AiA_iAi​라고 했을 때, 재환이는 AiA_iAi​이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다.가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력구현private static int dp(int index, int count)현재 위치가 index이고, 뛴 횟수가 count일 때 끝까지 갈 때의 최소 점프 횟수 반환하는 메소드끝에 도달한 경우 (index == N-1)현재까지 뛴 횟수를 반환한다.캐시값이 존재하는 경우 (cache[index][count] ≠ -2)캐시값을 반환한다.갈 수 있는 경로를 탐색한다.범위는 [1, A[index]] 이다.만약 뛰는 거..

[BOJ/JAVA] 16974번: 레벨 햄버거

16974번: 레벨 햄버거https://www.acmicpc.net/problem/16974키워드레벨-0 버거는 패티만으로 이루어져 있다.레벨-L 버거는 햄버거번, 레벨-(L-1) 버거, 패티, 레벨-(L-1)버거, 햄버거번으로 이루어져 있다. (L ≥ 1)구현모든 버거의 상태를 문자열로 나타낼 수 없다. (메모리를 많이 잡아먹기 때문)각 레벨의 버거마다 버거의 사이즈, 버거에 들어가는 패티의 양을 저장한다.buggers[]patties[]위 두 배열을 dp를 사용하여 값을 저장한다.dp(int level)현재 레벨이 level-버거일 때 버거의 크기를 반환한다.level == 0 인 경우패티만 존재하므로 1 반환이미 계산한 값인 경우계산한 값 반환계산하기버거의 크기는 [번] [(level-1)-버거] ..

[BOJ/JAVA] 1351번: 무한 수열

1351번: 무한 수열https://www.acmicpc.net/problem/1351키워드무한 수열 A는 다음과 같다.A_0 = 1A_i = A_⌊i/P⌋ + A_⌊i/Q⌋ (i ≥ 1)N, P와 Q가 주어질 때, AN을 구하는 프로그램을 작성하시오.0 ≤ N ≤ 10^122 ≤ P, Q ≤ 10^9구현중요한 것은 N, P, Q의 범위가 매우 크다는 것이다.배열로 만들기에는 너무 크기 때문에, Map을 이용하여 필요한 데이터만 저장하도록 하자.int 대신 long 자료형을 이용하자statch HashMap cacheA_i에서 i일 때 A_i의 값을 저장한다.statc long dp(long index)index가 0인 경우1을 반환한다.캐시값이 존재하는 경우캐시값을 반환한다.A[index] = A_[i..

[BOJ/JAVA] 2302번: 극장 좌석

2302번: 극장 좌석문제 어떤 극장의 좌석은 한 줄로 되어 있으며 왼쪽부터 차례대로 1번부터 N번까지 번호가 매겨져 있다. 공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다. 예를 들어서, 입장권에 5번이 쓰여 있으면 5번 좌석에 앉아야 한다. 단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.https://www.acmicpc.net/problem/2302키워드공연을 보러 온 사람들은 자기의 입장권에 표시되어 있는 좌석에 앉아야 한다.단, 자기의 바로 왼쪽 좌석 또는 바로 오른쪽 좌석으로는 자리를 옮길 수 있다.“VIP 회원”들이 있다. 이 사람들은 반드시 자기 좌석에만 앉아야 하며 옆 좌석으로 자리를 옮길 수 없다.주어진 조건을 만족하면서 사람들..

[BOJ/JAVA] 11052번: 카드 구매하기

11052번: 카드 구매하기요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다. PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다. 카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.https://www.acmicpc.net/problem/11052키워드카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재민규는 돈을 최대한 많이 지불해서 카드 N..

[BOJ/JAVA] 5557번: 1학년

5557번: 1학년상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다. 예를 들어, "8 3 2 4 8 7 2 4 0 8 8"에서 등식 "8+3-2-4+8-7-2-4-0+8=8"을 만들 수 있다.https://www.acmicpc.net/problem/5557키워드마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀고 있다.상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다.상근이가 만들 수 있는 올바른 등식의 수를 구하는 프로그램구현초기값은 항상 맨 앞에 있는 숫자이다.결과..

[java] 2225번: 합분해

https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class java_2225 { static int N, K; static long cache[][]; static long ..

15817번: 배수 공사

https://www.acmicpc.net/problem/15817 15817번: 배수 공사 합친 파이프의 길이 x를 만들 수 있는 방법의 수를 출력한다. 방법의 수가 2,147,483,647를 넘는 경우는 없다. www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; public class java_15817 { static int pipes[]..

11066번: 파일 합치기

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; import java.util.Arrays; import java.util.StringTokenizer; ..