2학년 2학기 알고리즘 과제_1주차(백준_1932번:정수 삼각형)

 📌 1주차 과제 2

 

 

문제

        7
      3   8
    8   1   0
  2   7   4   4
4   5   2   6   5

위 그림은 크기가 5인 정수 삼각형의 한 모습이다.

맨 위층 7부터 시작해서 아래에 있는 수 중 하나를 선택하여 아래층으로 내려올 때, 이제까지 선택된 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하라. 아래층에 있는 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 있는 것 중에서만 선택할 수 있다.

삼각형의 크기는 1 이상 500 이하이다. 삼각형을 이루고 있는 각 수는 모두 정수이며, 범위는 0 이상 9999 이하이다.

입력

첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다.

출력

첫째 줄에 합이 최대가 되는 경로에 있는 수의 합을 출력한다.

 

 

 

 📌 내 생각(풀이)

 

일단 문제를 보면 크기가 5인 정수 삼각형인데, 맨위층 7부터 아래 수들 중 하나를 택해 아래층으로 내려올 때, 선택한 수의 합이 최대가 되도록 해야한다.

아래층 수는 현재 층에서 선택된 수의 대각선 왼쪽 또는 대각선 오른쪽에 잇는 것 중에서만 선택가능하다.

해당문제는 배열로해서 구했을때 최대가 되는 값을 구하도록 구성해야할 것 같다.

파이썬을 풀거라면, for문을 통해서 구현을 해야할 것 같고, 오른쪽 대각선과 오른족 대각선 중 누적을 해야하므로 append함수를 구현해야할 것이다.

 

 

 📌코드 및 코드 해석

# 입력받을 숫자의 개수 n
n = int(input())

d = []
for i in range(n):
  
  # 각 행의 숫자들을 입력받아 리스트에 추가하기
    d.append(list(map(int, input().split())))

# 삼각형의 두 번째 행부터 시작
for i in range(1, n):
    for j in range(len(d[i])):
        # 첫 번째 열 처리: 위의 행의 첫 번째 열과 더하기
        if j == 0:
            d[i][j] = d[i][j] + d[i-1][j]
        # 마지막 열 처리: 위의 행의 마지막 열과 더하기
        elif j == len(d[i]) - 1:
            d[i][j] = d[i][j] + d[i-1][j-1]
        # 중간 열 처리: 위의 두 열 중 큰 값을 더하기
        else:
            d[i][j] = max(d[i-1][j-1], d[i-1][j]) + d[i][j]

# 마지막 행에서 최대값 출력하기
print(max(d[n-1]))

 

해당 알고리즘은 다이나믹 프로그래밍으로 풀어야한다.

이 코드는 주어진 숫자로 이루어진 삼각형 형태의 데이터를 입력받아, 가장 큰 경로의 합을 구하는 알고리즘이다.

 

하나씩 적어가면서 규칙을 찾아야한다.

d[0][0]=7
d[1][0]=3+7, d[1][1]=8+7
d[2][0]=8+d[1][0], d[2][1]=1+max(d[1][0],d[1][1]),
d[2][2]=0+d[1][1]

d[3][0]=2+d[2][0], d[3][1]=7+max(d[2][0],d[2][1]),
d[3][2]=4+max(d[2][1],d[2][2]), d[3][3]=4+d[2][2]

각 라인의 처음과 끝은 바로 위에 숫자를 더해주고, 나머지는 왼쪽 대각선, 오른쪽 대각선 중 최댓값을 더해나가 계속 누적해서 더해가도록해야한다.

 

1) 입력하기

n은 삼각형의 행 수를 나타내고, 이후 각 행의 숫자를 입력받아 2차원 리스트 d에 저장한다.

 

2)경로 합 계산하기

• 삼각형의 두 번째 행부터 시작하여 각 요소의 값을 갱신
• 첫 번째 열의 요소는 위의 행의 해당 요소만 더하고,
• 마지막 열은 위의 행의 마지막 요소와 더한다.
• 중간 열은, 위의 행에서 해당 요소의 왼쪽과 오른쪽의 최대값을 더한다.
• 이 과정을 통해 해당 경로의 최대 합을 나타낼 수 있음.

 

3)결과 출력하기

• 마지막 행에서 가장 큰 값을 찾아 출력한다. 이는 삼각형의 꼭대기에서 바닥까지 내려가는 경로 중 최대 합을 나타내도록 한다.

 

 

 

이제 학기 시작했으니까 열심히 알고리즘 공부를 해야겠다는 생각이 마구들었다..!

알고리즘 과제 끝!

 

 

[참고 자료]

 

https://velog.io/@bye9/%EB%B0%B1%EC%A4%80%ED%8C%8C%EC%9D%B4%EC%8D%AC-1932-%EC%A0%95%EC%88%98-%EC%82%BC%EA%B0%81%ED%98%95

[백준/파이썬] 1932 정수 삼각형