[boj] 22114번: 창영이와 점프

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

22114번: 창영이와 점프

 

 

 

1. 문제 설명 

N개의 블록이 존재한다. 각 블록은 창영이와 가까운 순서대로 1,2,3...,N-1,N번 블록이라고 한다. i번 블록과 i+1번 블록은 길이 Li만큼 떨어져 있는데 한 걸음에 길이 K만큼 이동할 수 있다. (Li <= K) 단, 최대 한 번은 블록의 길이와 상관 없이 i번에서 i+1번 블록으로 이동할 수 있다. 만약 다음 블록을 밟을 수 없다면 (Li > K and 최대 한 번의 이동도 이미 사용한 경우) 기록은 끝난다. (뒤로 돌아가서 다시 밟았던 블록을 밟는 경우는 없다고 가정) 최적의 시작점을 찾아서 최대 몇 개의 블록을 연속적으로 밟을 수 있는지 찾는다.

 

 

 

 

2. 접근 방식 

혼자 힘으로 해결하지 못하였다. 고수의 도움을 받은 아이디어이다.

N개의 블록에서 K보다 작은 블록은 신경쓰지 않고, Li > K인 블록만 다룬다. 문제의 예제 1번을 살펴본다. 

7 3
2 3 1 5 3 5

7개의 블록 중 Li > K인 거리 즉, K 보폭으로 이동할 수 있는 블록의 경우는 두 가지(5, 5)이다. 해당 블록을 섬이라고 바꿔 부르겠다. 다시말해서 창영의 보폭 K로 이동할 수 없는 섬은 두 가지인 셈인데 문제에서 요구하는 것은 "최적의 시작점을 찾아서 최대 몇 개의 블록을 연속적으로 밟을 수 있는지"이다. 거리를 무시할 수 있는 기회는 단 1번! 그렇다면 섬을 기준으로 최대한 밟을 수 있는 블록을 찾을 수 있지 않을까? 

 

1. 섬 = k 보폭으로 이동할 수 없는 곳 

2. 최대 1번의 기회를 통해 이동할 수 없는 거리를 이동할 수 있음

 

두 가지를 활용해서 문제를 해결해본다. 

 

 

 

 

3. 주석 달기 (변수 설명, 각 줄마다 문장으로 설명, 함수 설명)

import sys
input = sys.stdin.readline
n, k = map(int, input().split()) # 보도블럭의 개수 n, 창영이의 보폭 k
dist = list(map(int, input().split())) # 보도블럭 사이의 거리를 담는 배열
pos, dp = [], [] # 섬까지의 거리를 담는 배열 pos, 연속하는 두 수의 합을 저장할 배열 dp
cnt = 1 # 밟은 보도블록 카운팅할 변수
for i in dist: # 각 보도블럭 사이의 거리를 탐색하면서 
    if k < i: # 그 거리가 k보다 크면(섬이라면)
        pos.append(cnt) # pos에 지금까지 밟은 보도블럭의 수를 저장하고
        if cnt > 1: # 누적합이 2이상이라면 
            cnt = 1 # 초기화 
    else: # Li <= k 라면 
        cnt += 1 # 밟은 보도블럭의 수 1 증가 
if cnt: 
    pos.append(cnt)
    cnt = 0

if len(pos) < 2:  # k와 각 Li가 모두 같은 값일 때, pos배열의 길이는 1인 경우도 존재한다.
    # ex) 
    # 5 1
    # 1 1 1 1 1
    print(*pos)

else: # pos배열의 길이가 2이상인 경우 연속하는 두 값들을 더해 저장해준다.
    for i in range(1, len(pos)):
        dp.append(pos[i-1] + pos[i]) 
    print(max(dp))

 

 

 

 

4. 분석

Time : O(n)
Space : O(n)
소요시간 : 2시간
제출 횟수 (무작정 제출하기 않기)  : 10회
어려웠던 부분과 해결한 방법 : 아이디어 자체가 떠오르지 않아 힘들었다. dp인 것은 확실했으나 제대로 구상되지 않았다...
실수가 줄어들었는가 ? ㅠㅠ