[HackerRank] Jumping on the Clouds

문제

요약하자면, 구름을 밟고 건너가는 게임이 있는데, 오직 현재 적란운보다 1 또는 2만큼 건너 뛸 수 있으며, 적란운만 밟을 수 있고, 뇌우는 피해야한다.

시작 위치에서 마지막 구름까지 점프하는 데 필요한 최소 점프 횟수를 결정해야한다.

0은 밟을 수 있는 구름, 1은 피해야 하는 구름인데, 위 주어진 c를 보면 2가지 방법이 있다.

1) 0,2,4,6 번째 index를 가진 원소를 밟고 건널 수 있고,

2) 0,2,3,4,6 번째 index를 가진 원소를 밟고 건널 수 있다.

1번은 3번의 step, 2번은 4번의 step을 사용하였으므로, 반환 값은 3이 되어야한다.

 

코드

# import numpy as np
# import collections as co
"""
- n : 총 구름 수
- c : 구름 list
"""

def jumpingOnClouds(c):
    n = len(c)
    dp = [0] * n
    dp[0] = 0
    dp[1] = -1 if c[1] == 0 else 0
    # dp[2] = -1

    if n == 2:
        return 1

    for i in range(2, n):
        if c[i] == 1:
            dp[i] = dp[i - 1]
        elif c[i] + c[i-1] + c[i-2] == 0:         # all zero
            dp[i] = dp[i-2] - 1
        else:
            dp[i] = dp[i-1] - 1

    return -min(dp)

if __name__ == '__main__':

    n = 7
    c = [0, 0, 1, 0, 0, 1, 0]
    c2 = [0, 0, 0, 1, 0, 0]
    c3 = [0, 1, 0, 0, 1, 0]


    print(jumpingOnClouds(c))
    print(jumpingOnClouds(c2))
    print(jumpingOnClouds(c3))

 

풀이

1. 쉬운 다이나믹 프로그래밍으로 풀면 된다.(쉬운걸 왜 1시간 넘게 풀었는지,,ㅠ)
2. 케이스만 잘 나눠서 풀면 됨