[코테] DFS, DP_ 김밥천국

 

백준 28069번 : 김밥천국의 계단 _ Gold5 

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

 

수많은 메모리 초과, 시간초과, 현실 부정(중간의 맞았습니다는 내가 푼게 아니라 정답이 있긴 한거? 하고 다른 사람 정답 풀이를 넣어봤다. 🥲) 끝에 통해 풀이한 문제. 

문제 풀이 전부 정리할건 아니고, 내가 이 문제를 풀면서 어떤 논리를 놓치고 있었는지 정리해보려 한다. 

 

 

📌 키워드 

- BFS

- DP (나는 BFS로 풀이하였는데, DP로 더 간결하게 풀이할 수 있다.)

-  최소 횟수(거리) M만큼 이동하여 N에 도달할 수 있을때,  K >  M 이라면 K만큼 이동하여  N에 도달할 수 있는가? 

 

 

📌 문제 이해 

이 문제의 핵심은 세번째 키워드를 이해하는 것이다. 
문제에서 묻는 건

“0번 계단에서 시작해서 딱 K번의 행동 후에 정확히 N번 계단에 있을 수 있느냐?”

이다. 

그렇다면 우리는 그래프 탐색을 통해 어떻게든 정답을 찾아낼 수 있을 것이라는건 안다. 

그런데 문제는 메모리 초과와 시간 초과이다. 

 

Jump or 한칸을 선택하며 K번째 시도와 N번째 계단이 정확이 들어 맞는 시점을 찾아나가려다 보면, N번째 계단에 K이하의 횟수로 도달할 수 있음을 확인하더라도 그 들어맞는 시점을 찾기위해 훨씬 많은 노드를 만들고 탐색하게 된다.  K, N < 1000,000이기 때문에 N에 대해 중복적으로 노드를 생성한다면 메모리와 시간을 초과할 수 밖에 없다. 

 

dist[N] <= K 이면 K번의 행동후에 정확히 N번 계단에 있을 수 있다는 것을 이해하면, 같은 계단 위치에 대해서는 재탐색하지 않을 수 있다. 

 최소 이동 횟수 M은 "가장 빨리 도달하는 방법이다."

 

• 우리는 0에서 N까지 가는 여러 경로(행동 조합)를 만들 수 있지만,
  그중에서 가장 적은 행동 횟수를 쓰는 것이 "M"입니다.
• 예를 들어 N=6이라면
  0→1→2→3→4→6 이 순서대로 가면 5번의 행동으로 도달하므로
  “최소” M=5가 됩니다.

그렇다면 K번째에 N에 딱 맞춰서 도달하려면? 

1. K < M 일때  불가능 

• 가장 빨리 가도 M번이 걸리는데, 그보다 작은 K만큼의 행동으로는 절대 도달할 수 없음 

2.  K > N  일때  불가능 

• 가장 느리게 가는 방법은 전부 +1 만 해서 가는건데, 그보다 많은 횟수가 걸린다면 N+1 이상으로 올라가 버림 

3. M <= K <= N 일때 가능 

 

• 만약 K가 M보다 크다면,
  일부 “점프(+⌊i/2⌋)” 대신에 “한 칸씩(+1)”을 써서
  행동 횟수를 조금 늘려서 N에 맞출 수 있음 
• 반대로 K가 N보다 작거나 M보다 작으면 안 되고,
• 이 사이에 있는 모든 정수 K에 대해
  “점프와 +1의 조합”을 잘 치환하면 딱 K번에 N에 도달할 수 있음.

 

 

 

- 왼쪽은 level == K 이고, Node position == N 을 만족하는 순간을 찾기 위해 탐색하는 과정이고

- 오른쪽은 M <= K <= N 임을 이해하고 N에 도달한 즉시 visited[N] 을 방문처리하여 중복 탐색을 진행하지 않는 과정이다. 

한눈에 보기에도 탐색의 횟수가 확연히 차이나는 것을 볼 수 있다. 

 

 

EX1 ) 6 번째 계단에 6번째 이동 만에 갈 수 있는가?

오른쪽 그림을 통해 알 수 있듯이 K == 6,  N == 6 일때 
최소 도달 가능 횟수 M == 5 이다. 그리고 가장 느리게 도착하는 횟수는 N, 즉 6임을 알 수 있다. 

따라서 M <= K <= N을 만족하므로 6번의째 이동에 정확히 N에 도달할 수 있으므로 "minigimbab"을 출력한다.

 

EX1 ) 3 번째 계단에 4번째 이동 만에 갈 수 있는가?

N == 3, K == 4 인 경우,
그림을 통해 3에 도달 하는 최소 횟수 M == 3 임을 알 수 있다.
이는 K > N 이므로 불가능하여 water을 출력한다.

 

📌 정리

문제를 풀이하기 전에, 빠르게 논리를 정리를 하고 시작하려는 편인데, 계속 틀리는 상황에서 입력, 로직, 출력을 아래와 같이 정리하고 넘어갔다.

 

K번째 행동에서 N번째 계단에 정확히 도달하는 문제가 주어진다면, 다음에는 이렇게 정리할 수 있을것 같다.