BOJ - 점프2253 [DP] Java

하반기 코딩테스트를 치루며, DP 관련해서 문제가 자주 출제되었다고 생각한다. 어떤 회사의 코딩테스트인지는 밝히지 못하겠지만, 해당 문제와 비슷하게 풀었던 문제가 기억나서 글을 작성하였다.

 

추가로 해당 문제를 풀이한 언어로 Java 코드는 없었고, 대부분 파이썬과 C++로만 정리되어 있어, 풀이에 어려움을 겪을 분들에게 정답을 공유하고자 작성했다. 정답 풀이는 아래 Github 링크에 있고, 개인적으로 고민하며 해결함을 바랬기에 제 코드 위주로 구조적인 힌트만 간략하게 작성하였다.

 

https://github.com/himJJong/codingtest_study/blob/master/24_11_04/boj_%EC%A0%90%ED%94%84.java

codingtest_study/24_11_04/boj_점프.java at master · himJJong/codingtest_study

 

점프 문제 해결하기: DP를 활용한 접근

문제 개요

- 입력:

• N: 목표 위치
• stone_n: 금지된 돌의 개수
• 금지된 돌의 위치 리스트

- 출력:

• 최소 점프 횟수 또는 도달할 수 없는 경우 -1 출력

 

1. 입력 처리

코드의 첫 부분은 사용자로부터 입력을 받습니다. BufferedReader를 사용하여 효율적으로 입력을 처리하고 있습니다.

 

2. 금지된 돌의 위치 저장

다음으로, 금지된 돌의 위치를 HashSet에 저장합니다. HashSet은 O(1) 시간 복잡도로 존재 여부를 확인할 수 있어 매우 효율적입니다.

 

3. DP 배열 초기화

DP 배열을 초기화합니다. 이 배열은 각 위치에서 가능한 속도에 대한 최소 점프 횟수를 저장합니다.

- maxV는 최대 속도를 계산합니다. 해당 위치에 도달할 수 있는 최대 속도를 결정합니다.
- dp 배열을 10001로 초기화하여 최소 점프를 찾을 수 있도록 합니다.

 

4. 시작 위치 초기화

 

5. DP를 통한 최소 점프 횟수 계산

이제 실제로 DP를 통해 최소 점프 횟수를 계산합니다. 각 위치에 대해, 가능한 모든 속도에 대해 점프를 계산합니다.

- 금지된 돌에 도달하는 경우는 건너뛰고,
- 현재 위치에서 가능한 속도 범위에 대해 점프를 계산합니다.

 

6. 결과 계산 및 출력

마지막으로, 목표 위치 N 에 도달했을 때의 최소 점프 횟수를 계산합니다. 모든 속도에 대해 최솟값을 구하고, 결과를 출력합니다.

주어진 위치에 도달하기 위한 최소 점프 횟수를 효율적으로 계산하는 알고리즘입니다. DP를 활용하여 각 위치와 속도에 대한 최소 점프 수를 기록하며, 금지된 위치를 고려하는 점이 주요한 특징이며, 다양한 최적화 문제에 응용될 수 있습니다.