[Python] 22114. 창영이와 점프

https://www.acmicpc.net/problem/22114

22114번: 창영이와 점프

 

접근법

• 입력으로 i번과 i+1번 간 길이들이 주어지기 때문에 L_list에 0번째에 0을 넣어줌
• result[0]에는 점프를 하지 않은 경우를, result[1]에는 점프를 한 경우를 dp를 활용하여 저장
  • result[0][i] : 점프를 하지 않고 i에 도달했을 때 밟은 블록 수
  • result[0][j] : 점프를 1번 하고 i에 도달했을 때 밟은 블록 수

def input_func():
    N, K = map(int, input().split())
    L_list = [0] + list(map(int, input().split()))
    return N, K, L_list

def solution(n, k, l_list):
    result = [[0 for _ in range(len(l_list))] for _ in range(2)]
    # result[0] : 점프를 하지 않은 경우
    # result[1] : 점프를 한 경우
    result[0][0] = 1
    result[1][0] = 1
    max = 0
    
    for i in range(len(l_list)):
        if l_list[i] <= k: # 이동 가능한 경우
            result[0][i] = result[0][i-1] + 1
            result[1][i] = result[1][i-1] + 1
        else: # 이동 불가능한 경우
            result[0][i] = 1 # 첫 블록으로 초기화
            result[1][i] = result[0][i-1] + 1 # 점프를 하지 않고 i-1번째에 도착한 경우 + 1

        # 최대값 저장
        if result[0][i] > max:
            max = result[0][i]
        if result[1][i] > max:
            max = result[1][i]
    print(max)


def main():
    n, k, l_list = input_func()
    solution(n, k, l_list)

if __name__ == '__main__':
    main()

---

사용된 알고리즘

다이나믹 프로그래밍