250x250
반응형
Notice
Recent Posts
Recent Comments
Link
종식당
[백준 1932] 정수 삼각형 본문
728x90
반응형
https://www.acmicpc.net/problem/1932
- 문제설명
삼각형 모양으로 정수들이 주어지는데 맨 위층부터 아래로 내려오면서 숫자를 층마다 하나씩 선택하게 된다. 선택한 값들의 합이 최대가 되는 숫자를 출력하면 된다. 이때 선택할 수 있는 값을 바로 위 층에서 왼쪽 대각선 오른쪽 대각선에서만 선택할 수 있다.
- 제출코드
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
int [][] lst = new int[n+1][n+1];
int [][] dp = new int[n+1][n+1];
for(int i = 1; i <= n; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 1; j <=i; j++){
lst[i][j] = Integer.parseInt(st.nextToken());
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <=i; j++){
dp[i][j] = lst[i][j] + Math.max(dp[i-1][j-1],dp[i-1][j]);
}
}
int max = -1;
for(int i = 1; i<=n; i++){
if(dp[n][i] > max){
max = dp[n][i];
}
}
System.out.println(max);
}
}
코드설명
먼저 lst 2차원 배열을 만들어서 입력으로 받은 숫자들을 배열에 담아준다.
그러면 다음과 같이 배열에 담길 것이다.
그리고 dp배열을 하나 만들어 준다. 위에서부터 아래로 내려오면서 사진처럼 배열에 담았을 때 생각해 보면 바로 위의 값과 왼쪽 대각선의 값들 중에서 더할 값을 선택할 수 있다. 더했을 때 가장 큰 값이 되어야 하므로 max함수를 사용해서 두 값들 중에 큰 값을 선택해 해당 인덱스와 더해주면 된다. 그럼 이 dp배열에서 해당 인덱스는 거기까지의 최댓값이 저장되어 있는 셈이다.
dp [i][j] = lst [i][j] + Math.max(dp [i-1][j-1], dp [i-1][j]);
위 코드를 가지고 for문을 돌면서 해당 인덱스까지 오면서의 최댓값을 각각의 index에 저장해 둔다.
그럼 마지막 행에서 최댓값을 출력해 주면 그 값이 정답이다.

728x90
반응형
'백준' 카테고리의 다른 글
[백준 14719 with JAVA] 빗물 (3) | 2025.01.29 |
---|---|
[백준 7562] 나이트의 이동 (1) | 2025.01.06 |
[백준 9095] 1, 2, 3 더하기 (2) | 2024.12.16 |
[백준 9935] 문자열 폭발 (0) | 2024.11.01 |
[백준 3050] 나머지 (0) | 2024.09.28 |