Problem Solving1233 [백준] 15489 파스칼 삼각형 - Dynamic Programming / Java • 문제 링크 15489번: 파스칼 삼각형 첫째 줄에 양의 정수 R, C, W가 공백을 한 칸씩 두고 차례로 주어진다. (단, 2 ≤ R+W ≤ 30, 2 ≤ C+W ≤ 30, 1 ≤ W ≤ 29, C ≤ R) www.acmicpc.net • 풀이 과정 위 꼭짓점이 r, c 이고 변의 길이가 w 인 정삼각형을 포함하는 범위까지 파스칼 삼각형을 구한다. 이는 2차원 배열에서 계단 형태를 띄며 각 좌표의 값은 좌상단 값과 상단 값을 합한 값이 된다. 이 후 문제에 주어진 정삼각형의 범위의 모든 값을 합한 값을 출력한다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import j.. 2023. 3. 28. [백준] 14430 자원 캐기 - Dynamic Programming / Java • 문제 링크 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net • 풀이 과정 현재 지점에서 오른쪽 또는 아래로만 이동 가능하므로, 이는 특정 지점 i, j 의 이전 지점은 i - 1, j 와 i, j - 1 중 하나가 된다. 따라서 이 두 지점 중 큰 값이 이전 지점이 되야 최대로 자원을 수집할 수 있다. 이는 코드 상에서 dp[i][j] += Math.max(dp[i - 1][j], dp[i][j - 1]) 와 같이 표현할 수 있다. • 풀이 코드 import java.io.Buffere.. 2023. 3. 27. [백준] 1793 타일링- Dynamic Programming / Java • 문제 링크 1793번: 타일링 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 정수 n이 주어진다. www.acmicpc.net • 풀이 과정 문제의 타일링 방법을 배열을 활용한 점화식으로 나타내면 dp[n] = dp[n - 1] + dp[n - 2] * 2 가 성립한다. 다만 long 범위를 벗어나는 문제의 출력범위를 표현하기 위해서는 Java 에선 BigInteger 를 활용한다. n의 범위가 최대 250 이므로, 모든 경우의 수를 구하고 입력받은 타일 길이의 경우의 수를 도출할 수 있지만, 해당 풀이에서는 입력 중 최대 값을 먼저 구해 해당 범위까지만 경우의 수를 구하였다. • 풀이 코드 import java.io.BufferedReader; im.. 2023. 3. 26. [백준] 18353 병사 배치하기 - Dynamic Programming / Java • 문제 링크 18353번: 병사 배치하기 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 2,000) 둘째 줄에 각 병사의 전투력이 공백을 기준으로 구분되어 차례대로 주어진다. 각 병사의 전투력은 10,000,000보다 작거나 같은 자연수이다. www.acmicpc.net • 풀이 과정 배치하고자하는 병사 형태는 최장 증가 부분 수열이므로, 병사의 수 n에 최장 증가 부분 수열의 길이를 뺀 값이 열외해야 하는 병사의 수가 된다. • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStrea.. 2023. 3. 25. [백준] 13699 점화식 - Dynamic Programming / Java • 문제 링크 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net • 풀이 과정 • 풀이 코드 import java.io.BufferedReader; import java.io.BufferedWriter; import java.io.IOException; import java.io.InputStreamReader; import java.io.OutputStreamWri.. 2023. 3. 24. [백준] 2358 평행선 - Data Structure / Java • 문제 링크 2358번: 평행선 첫째 줄에 n(1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 각 점의 좌표가 주어진다. 같은 좌표가 여러 번 주어질 수 있으며, 그런 경우 서로 다른 점으로 간주한다. 좌표는 절댓값이 231보다 작 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.HashMap; import java.util.Map; import java.util.Str.. 2023. 3. 23. 이전 1 ··· 148 149 150 151 152 153 154 ··· 206 다음
