[백준1932번][백준][baekjoon][1932번][DynamicProgramming][DP][정수삼각형][Python][파이썬]

문제링크

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

1932번: 정수 삼각형

문제

 

풀이

이번 문제는 계단 오르기 등의 문제와 유사하며 DP를 활용하면 쉽게 해결할 수 있는 문제입니다. 배열에 삼각형 모양으로 이루어진 값들이 입력되는 것만 신경 쓰시면 어렵지 않게 해결 가능할 것 같습니다. 다른 분들은 어떨지 모르겠지만 저는 1차원 배열을 사용하여 입력값의 순서대로 배열을 생성하였습니다. 즉, 삼각형의 맨 윗부분이 배열의 0번 인덱스에 들어가도록 했습니다. 조금 생각하고 까다로운 조건은 삼각형에서 대각선 왼쪽 또는 오른쪽에 있는 곳으로만 이동이 가능하다는 점이 되겠습니다. 문제 접근은 다음과 같습니다.

 

1. 모든 입력을 1차원 배열에 저장한 후 DP 테이블을 생성한다.

2. 각 층의 첫 번째 위치를 저장할 수 있는 변수를 따로 저장한다.

3. 삼각형의 바로 왼쪽 위에 있는 값은 배열의 인덱스(현재 위치)에서 현재 층만큼을 빼준 값이다.

- 예제 입력에서 7이 있는 위치를 1층, 3 8 이 있는 위치를 2층 이런 식으로 가정했습니다.

- 1층 7번의 인덱스는 0이며, 2층의 3의 인덱스는 1, 3층 8번의 인덱스는 3입니다.

- 3층 1에서 2층 3으로 이동하기 위해서는 인덱스 4(3층 1번 위치)에서 현재 층 3을 빼면 접근할 수 있습니다.

4. 삼각형의 바로 오른쪽 위에 있는 값은 배열의 인덱스(현재 위치)에서 현재 층-1 만큼을 빼준 값이다.

- 3층 8에서 2층 3으로 이동하기 위해서는 인덱스 3(3층 8번 위치)에서 현재 층-1 인 2를 빼면 접근할 수 있습니다.

 

이런 방식으로 접근 가능한(왼쪽 대각선, 오른쪽 대각선) 방향으로의 합을 DP 테이블에 저장하였습니다. 하나의 조건이 더 필요한데, 각 층의 맨 왼쪽 값은 오른쪽 위로만 이동 가능하고 맨 오른쪽 값은 왼쪽 위로만 이동이 가능한 점입니다. 점화식으로 작성하면 다음과 같이 작성 가능하겠습니다. 설명의 편의상 point는 삼각형에서 현재 위치에 있는 값을 의미하며, step은 삼각형에서 현재 층을 의미합니다.

 

IF N이 삼각형에서 맨 왼쪽의 값일 때 :

- D[N]=D[N-step+1]+point

IF N이 삼각형에서 맨 오른쪽의 값일 때 :

- D[N]=D[N-step]+point

ELSE:

- D[N] = ( D[N-step+1], D[N-step] 중 큰 값) + point

 

 

소스코드

#python

testcase=int(input())
 
dp=[ 0 for _ in range(250004) ]
step=[ i for i in range(501) ]
start_point=1
maxnum=0
 
for i in range(1, testcase+1):
    
    start_point+=(i-1)
    if i==1:
        dp[start_point]=int(input())
 
    else:
        step=[ i for i in input().split(' ') ]
        for j in range(i):
            if j==0:
                dp[start_point]=dp[start_point-i+1]+int(step[j])
            elif j==i-1:
                dp[start_point+j]=dp[start_point+j-i]+int(step[j])
            else:
                if dp[start_point+j-i]> dp[start_point+j-i+1]:
                    dp[start_point+j]=dp[start_point+j-i]+int(step[j])
                else:
                    dp[start_point+j]=dp[start_point+j-i+1]+int(step[j])
                        
 
for i in range(testcase):
    if dp[start_point+i]>maxnum:
        maxnum=dp[start_point+i]
 
print(maxnum)
 
 
 

 

오류 또는 더 좋은 풀이 방법이 있다면 댓글로 남겨주세요.

이번 포스팅에서는 python으로 작성하였지만, 추후 C와 C++ 코드도 올리도록 하겠습니다.