[BOJ/백준] 1932 정수 삼각형

● [문제번호 1932] 정수 삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

 

● 풀이 과정

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[row][col] : 맨 위층에서 row행 col열 까지 경로의 최대합

 

2. 점화식 찾기

→ 문제에서 그려진 예각삼각형이 아닌 입력할때 처럼 생긴 직각삼격형으로 생각한다.

그러면 맨 위층에서 내려갈때(row가 커질 때) 자신과 동일한 col이거나 자신보다 1 큰 col+1 로 내려갈 수 있다.

dp[row + 1][col] = max(dp[row + 1][col], dp[row][col] + num[row + 1][col])
dp[row + 1][col + 1] = max(dp[row + 1][col + 1], dp[row][col] + num[row + 1][col + 1])

 

 

3. 초기값 정하기

→ 맨 위층만 정하면 된다.

dp[1][1] = num[1][1]

 

예제 입력1 풀이과정

 

 

● 주의 할 것

: NULL

 

● 참고 할 것

: NULL

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// num : 정수 삼각형
// dp[row][col] : 맨 위층에서 row행 col열 까지 경로의 최대합
int num[501][501];
int dp[501][501];
int N;

void triangle()
{
    // 초기값
    dp[1][1] = num[1][1];
    
    // 점화식
    for(int row = 1; row < N; row++)
    {
        for(int col = 1; col <= row; col++)
        {
            dp[row + 1][col] = max(dp[row + 1][col], dp[row][col] + num[row + 1][col]);
            dp[row + 1][col + 1] = max(dp[row + 1][col + 1], dp[row][col] + num[row + 1][col + 1]);
        }
    }
}


int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    
    // 정수 삼각형 입력
    for(int row = 1; row <= N; row++)
        for(int col = 1; col <= row; col++)
            cin >> num[row][col];
    
    triangle();
    
    // 맨 아래층 중에서 가장 최대값을 찾기
    int sol = 0;
    for(int col = 1; col <= N; col++)
        sol = max(sol, dp[N][col]);
    
    cout << sol;
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [401 - 다이나믹 프로그래밍 1 (연습)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	15988	1, 2, 3 더하기 3	https://pirateturtle.tistory.com/214
2	1149	RGB거리	https://pirateturtle.tistory.com/215
3	1309	동물원	https://pirateturtle.tistory.com/216
4	11057	오르막 수	https://pirateturtle.tistory.com/217
5	9465	스티커	https://pirateturtle.tistory.com/218
6	2156	포도주 시식	https://pirateturtle.tistory.com/219
7	1932	정수 삼각형	https://pirateturtle.tistory.com/220
8	11055	가장 큰 증가 부분 수열	https://pirateturtle.tistory.com/221
9	11722	가장 긴 감소하는 부분 수열	https://pirateturtle.tistory.com/222
10	11054	가장 긴 바이토닉 부분 수열	https://pirateturtle.tistory.com/223
11	13398	연속합 2	https://pirateturtle.tistory.com/224
12	2133	타일 채우기	https://pirateturtle.tistory.com/225