[프로그래머스] 코딩테스트 고득점 Kit - DP (파이썬)

💻 N으로 표현 (level 3)

def solution(N, number):
    if number == 1:
        return 1
    set_list = []
    
    for cnt in range(1, 9): # 1개부터 8개까지 확인
        partial_set = set()
        partial_set.add(int(str(N) * cnt)) # 이어 붙여서 만드는 경우 넣기
        for i in range(cnt - 1): # (1, n-1) 부터 (n-1, 1)까지 사칙연산
            for op1 in set_list[i]:
                for op2 in set_list[-i - 1]:
                    print(f'op1 : {op1}, op2 : {op2}')
                    partial_set.add(op1 + op2)
                    partial_set.add(op1 * op2)
                    partial_set.add(op1 - op2)
                    if op2 != 0:
                        partial_set.add(op1 / op2)
        # 만든 집합에 number가 처음 나오는지 확인
        print(f'partial_set : {partial_set}')
        if number in partial_set:
            return cnt
        set_list.append(partial_set)
    return -1

solution(5,12)

• 이해하려고 print문 중간중간 끼웠음 알아서 떼서 쓰면 된다.
• 풀이법은 해당 블로그에 자세하게 나와있다.
• 
• 작은 문제를 큰 문제인 N의 개수와 연관짓는게 포인트!
• 지금까지 풀었던 dp 문제중에서 제일 어려운듯..

---

💻 정수 삼각형 (level 3)

def solution(triangle):
    L = len(triangle)
    dp = [[0] * L for _ in range(L)]
    dp[0][0] = triangle[0][0]
    
    for i in range(1, L):
        for j in range(len(triangle[i])):
            if j==0:
                dp[i][j] = dp[i-1][j] + triangle[i][j]
            elif j == len(triangle[i])-1:
                dp[i][j] = dp[i-1][j-1] + triangle[i][j]
            else:
                dp[i][j] = max(dp[i-1][j-1]+triangle[i][j], dp[i-1][j]+triangle[i][j])
            
    return(max(dp[L-1]))

• 양끝 값은 그 전 끝값이랑 단순히 더하기
• 중간 값은 점화식 참고

• 하고보니까 너무 정삼각형 형태를 생각했나 싶다
• 직각 삼각형으로 생각해도된다. 참고블로그

---

💻 등굣길 (level 3)

def solution(m, n, puddles):
    dp = [[0] * (m+1) for _ in range(n+1)]
    
    for i in range(1, n+1):
       for j in range(1, m+1):
            if [j, i] in puddles:
                continue
            if i == 1 and j == 1:
                dp[i][j] = 1
            else:
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % 1000000007
    
    return dp[n][m]

• 상하좌우로 움직이는 것도 아니고 최단경로의 수를 구하는 (누적합 느낌)거기 때문에 DP를 사용한다.
• 거지같은 함정이 있는데 return 값을 보면 dp[m][n] 이 아닌 dp[n][m] 으로 구하게 되어있다. 행과 열을 바꿔서 문제를 풀었다는 건데 그러면 paddles도 바꿔줘야 한다. (if [j, i] in puddles:)
• 이거 때문에 삼십분은 버린거 같다. 맞왜틀인거 같으면 그냥 구글링하자 정신건강에 좋다.

---