leetcode 322(dp), 983(dp), 289(비트 연산)

322 https://leetcode.com/problems/coin-change/

문제를 읽어보니 이전에 풀었던 백준 2293번 https://qkqhxla1.tistory.com/683 과 비슷하다. 여기서 코드를 가져와서 변형했다.

class Solution(object):
    def coinChange(self, coins, amount):
        dp = [999999 for i in xrange(amount+1)]
        dp[0] = 0
        for i in xrange(len(coins)): #모든 동전을 돌아가면서
            for j in xrange(1, amount+1): #1원~만들고자하는 k원까지
                if j >= coins[i]: #현재 동전으로 j원을 만들수있으면
                    dp[j] = min(dp[j], dp[j-coins[i]] + 1) #j원은 j-coin[i]개의 갯수로 만들수있다.
        if dp[amount] == 999999:
            return -1
        return dp[amount]

983 https://leetcode.com/problems/minimum-cost-for-tickets/

기차표를 사는 dp문제이다.

class Solution(object):
    def mincostTickets(self, days, costs):
        #days = [1,2,3,4,6,8,9,10,13,14,16,17,19,21,24,26,27,28,29]
        #costs = [3,14,50]
        INF = 999999
        dp = [INF for i in xrange(366)]
        dp[0] = 0
        day_list = set(days)
        for i in xrange(1, days[-1]+1):  # 날짜를 순회하면서
            if i not in day_list:  # 여행가는 날짜가 아니면 전날치까지의 최소치를 입력해놓는다.
                dp[i] = dp[i-1]
                continue
            dp[i] = min(dp[i-1] + costs[0], dp[max(i-7, 0)] + costs[1], dp[max(i-30, 0)] + costs[2])  # min(하루전 최소치 + 하루치, 1주일전 최소치(근데 0이하로 내려가면 안되므로 저렇게) + 1주일치, 30일전 최소치 + 30일치.)
        return dp[days[-1]]

289 https://leetcode.com/problems/game-of-life/

처음보고 문제를 못풀었다. 문제의 follow up 첫번째를 보면 in place로, 그러니까 주어진 배열 자체를 그때그때 바꾸는 방식으로 풀라고 한다. 가장 쉬운 방법인 리스트를 하나 더 복제해서 next상태를 만들어놓고 그걸 덮어씌우려고 했는데 그게 안된다는거였다. discussion을 보니 bit manipulation으로 잘 푼 아이디어가 있어서 그걸 가져왔다.

https://leetcode.com/problems/game-of-life/discuss/73223/Easiest-JAVA-solution-with-explanation

그리고 board가 무한대일때 어떻게 풀수 있을까? 하는 질문이 있는데 discussion에서 이것저것 읽어보자.

class Solution(object):
    def gameOfLife(self, board):
        def bfs(x,y):
            live = death = 0
            for idx in [[-1,1], [-1,0], [-1,-1], [0,1], [0,-1], [1,1], [1,0], [1,-1]]:
                if x + idx[0] < 0 or y + idx[1] < 0 or x + idx[0] > len(board)-1 or y + idx[1] > len(board[0])-1:
                    continue
                if board[x+idx[0]][y+idx[1]] & 1 == 1:
                    live += 1
                else:
                    death += 1
            cur_state = board[x][y] & 1
            if cur_state == 1 and 2 <= live <= 3:
                board[x][y] = 3
            elif cur_state == 0 and live == 3:
                board[x][y] = 2
                

        for i in xrange(len(board)):
            for j in xrange(len(board[i])):
                bfs(i, j)
                
        for i in xrange(len(board)):
            for j in xrange(len(board[i])):
                board[i][j] >>= 1