안녕하세요! 이틀간 푹 쉬다가 돌아온 쏘코입니다.
DP가 총 4문제인데, 가장 낮은 난이도가 레벨3이라는게 참 오묘합니다.
DP는 정말 구현보다 내가 맞는 알고리즘을 생각해냈는지가 굉장히 중요한 것 같아요.
이번 문제도 굉장히 재미있는 문제였습니다.
출처 : 프로그래머스 코딩테스트 연습 고득점 KIT, programmers.co.kr/learn/courses/30/lessons/43105
코딩테스트 연습 - 정수 삼각형
[[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] 30
programmers.co.kr
목차
0. 문제 설명
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.
삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.
0.0. 제한사항
- 삼각형의 높이는 1 이상 500 이하입니다.
- 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.
0.1. 입출력 예
| triangle | result |
| [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]] | 30 |
1. 풀이 과정
정말 간단합니다. dp문제라는 것을 염두에 두고 푼다면 금방 찾아내실 수 있을 것이고, 그게 아니더라도 조금만 생각하면 쉽게 떠올릴 수 있습니다.
저는 두 가지 방식을 생각했습니다. 처음에는 DFS방식으로 모든 경로를 탐색해서 최대값을 구하는 방식을 생각했습니다. 그런데 이 문제가 DP섹션에 있었다는 것을 생각해볼 때 이것은 바람직한 풀이법이 아니라고 생각했습니다.
그래서 다음에 떠올린 방법은 bottom-up방식입니다. 경로는 아래 2개의 수 중 더 큰 쪽으로 진행될 것이기 때문에, 아래서부터 붙어있는 2개를 비교해서 더 큰 것을 위쪽에 더해주는 방식입니다.
이미 존재하는 triangle vector를 이용해서 아래서부터 위로 올라가면서 확인합니다. 아래부터 돌기 때문에 삼각형의 단계를 나타내는 i는 거꾸로 진행되고, 단계 안에서 수의 순서를 나타내는 j는 그대로 앞에서부터 확인해도 무방합니다.
또한 triangle를 파라미터값으로 받을 때 call by value 방식으로 받아왔으므로 원본이 훼손되지 않습니다. 따라서 이미 존재하는 triangle에 더해주면서 올라가도 됩니다.
이런 식으로 끝까지 올라가서 triangle[0][0]까지 다 더해지면, triangle[0][0]을 answer에 넣어서 출력하면 끝입니다.
2. 소스 코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
int solution(vector<vector<int>> triangle) {
int answer = 0;
// 아랫쪽 열에 있는 친구들 중에 붙어있는 것들끼리 비교해서 큰 친구를 위와 더해준 후 sum에 넣는다. 이걸 반복!
for (int i = triangle.size()-1; i > 0 ; --i){
for(int j = 0; j < i; ++j){
triangle[i-1][j] += (max(triangle[i][j],triangle[i][j+1]));
}
}
answer = triangle[0][0];
return answer;
}
3. 후기
내가 생각하고 있는 것이 맞나..라는 의구심이 조금 드는 문제였습니다. level3이라고 해서 약간 쫄아있었던 것 같네요. level보다 어려운 문제가 있으면 level보다 쉬운 문제도 있을텐데라고 생각만 했었는데 이 문제는 그럭저럭 level3에서는 굉장히 쉬운 문제 축에 속하지 않을까 생각합니다.
top-down 방식으로 풀면 재귀함수를 사용하면 될 것 같습니다. DP문제에서 보통 top-down방식은 재귀, buttom-up방식은 반복문을 사용합니다. 이런 꿀팁만 알아놓으면 풀이시간이 훨씬 단축될 수 있으리라고 생각합니다 :)
최근댓글