✅ 문제풀이 - DP
🎈 정수 삼각형 (level 3)
위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중 거쳐간 숫자 합이 가장 큰 경우를 찾는 방법.
- 현재 칸 기준 아래 칸으로 이동할 수 있는 방법은 5시 or 7시
- 삼각형 배열인 triangle이 주어질 때 경로를 통해 거쳐간 숫자의 합을 최대가 되도록 리턴하는 문제.
def solution(triangle):
n = len(triangle)
start = triangle[0][0]
dp = [[0]*n for _ in range(n)]
dp[0][0] = start
for i in range(n-1):
for j in range(len(triangle[i])):
dp[i+1][j] = max(dp[i+1][j], dp[i][j] + triangle[i+1][j])
dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j] + triangle[i+1][j+1])
return max(dp[-1])< 문제 풀이 >
오랜만에 풀어보는 dp문제.
DP문제에서의 핵심은 비교 대상을 만들어주기 위해 zero로 filling한 빈 리스트를 생성해주는 것이 중요하다.
문제를 보자마자 triangle 형태로 맞춰주기 위해 len(triangle)를 n으로 두고 처리하였다.
dp초기값은 주어진 삼각 트리의 루트이므로 start로 처리한 변수를 dp초기값으로 두었다.
이후 아래칸으로 내려갈수록 값을 더해 더 큰값만을 다음 리스트 형태로 저장해주는 방식으로 처리하였고, 리턴으로 dp 리스트 중 마지막 리스트의 최댓값을 출력하도록 한다.
🎈 N으로 표현 (level 3)
✨ 추후 다시 풀어볼 문제 !!!!
숫자 n과 n에 사칙연산을 사용해 만들고자 하는 number가 주어질 때, n과 사칙연산만을 사용해 number로 만들 수 있는 여러 방법들 중 n 사용횟수가 최소인 수를 구하는 문제.
ex) (55+5) / 5 = 12 return : 4
def solution(N, number):
dp = [set() for _ in range(9)]
for i in range(1, 9):
dp[i].add(int(str(N) * i))
for j in range(1, i):
for op1 in dp[j]:
for op2 in dp[i-j]:
dp[i].add(op1 + op2)
dp[i].add(op1 - op2)
dp[i].add(op1 * op2)
if op2 != 0:
dp[i].add(op1 // op2)
if number in dp[i]:
return i
return -1< 풀이 과정 >
문제 푸는데 거의 1시간 넘게 걸려 다른 분들의 풀이를 참고하여 진행했다.
dp를 어떻게 구성해야할 지 모르는 게 가장 문제였다. 초기 dp 설정이 가장 중요한데, 각 숫자가 나온 횟수 만큼을 dp로 저장해놓는 것이 핵심이었다.간략하게 설명하면 N의 사용 횟수에 대한 dp 테이블을 만든 다음 n을 i번 사용해 만들 수 있는 수들을 나열하여 각 dp 내 인덱스 별로 값을 수정해주면 되는 문제.
문제 풀이를 하면 다음 과정을 거친다.
- set 형태로 9개 생성 : dp
- 초기 dp 설정으로써 for문으로 1~8까지만 돌며 dp 내 각 인덱스 별로 int(str(N) * i) 를 처리해 n을 1~8번 반복한 수를 집어넣는다. (i가 8이 넘어가면 -1로 처리하기에 9는 제외)
- 이후 1~i-1까지 탐색을 진행하며 j인덱스를 지정해주고 dp내 앞 순서부터 숫자 n을 i번만 사용해 만들 수 있는 가능한 모든 수들을 저장해준다.
- for 문으로 1~i-1을 한 번씩 돌고 난 후 dp[i] 내 표현해야 할 수 number가 있다면 해당 i를 출력하고, 없다면 모든 반복문이 끝난 후 -1을 리턴해준다.
실질적으로 시간복잡도는 O(N^3) 으로 길어봐야 2^9 밖에 안되고, 공간복잡도의 경우 dp 내 i번째 인덱스에 원소들이 지속적으로 아무리 추가되도 커봐야 8^2이 된다. 따라서 O(N^2)로 시간복잡도, 공간복잡도 모두 만족!
