Problem Solving1222 [백준] 17626 Four Squares - Dynamic Programming / Java • 문제 링크 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args).. 2022. 12. 6. [백준] 1965 상자넣기 - Dynamic Programming / Java • 문제 링크 1965번: 상자넣기 정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수가 www.acmicpc.net • 풀이 과정 문제에서 각 상자의 크기가 이전 상자의 크기보다 커야하고, 그러한 상자들의 개수를 가장 많이 선택할 수 있는 경우의 수를 구해야한다. 따라서 이는 최장 증가 부분 수열(LIS)를 구하는 문제이다. [백준] 11053 가장 긴 증가하는 부분 수열 - Dynamic Programming / Java • 문제 링크 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 .. 2022. 12. 5. [백준] 9655 돌 게임 - Dynamic Programming / Java • 문제 링크 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWriter; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(Syste.. 2022. 12. 4. [백준] 1010 다리 놓기 - Dynamic Programming / Java • 문제 링크 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. 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.StringTokenizer; public class Main { public static void main.. 2022. 12. 3. [백준] 1788 피보나치 수의 확장 - Dynamic Programming / Java • 문제 링크 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 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; public class Main { public static void main(String[] args) t.. 2022. 12. 2. [백준] 2302 극장 좌석 - Dynamic Programming / Java • 문제 링크 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 < 231-1) www.acmicpc.net • 풀이 과정 vip석에 따라 점화식 구조가 달라지므로 각각의 vip석 번호를 Set 에 저장해둔다. 만약 vip석이 존재하지 않는 경우, n = 0 ~ 4 까지의 경우의 수를 구해 규칙성을 찾아내면 dp[i] = dp[i - 1] + dp[i - 2] 의 점화식을 구할 수 있다. 하지만 현재 또는 이전 좌석이 vip석일 경우, (set.contains(i) || set.contains(i - 1)) 해당 좌석으로 자리 이동이 불가하므로 이전에 구해진 경우의 .. 2022. 12. 1. 이전 1 ··· 165 166 167 168 169 170 171 ··· 204 다음
