- 티어 : Sliver 1
- 정답여부 :
정답- 알고리즘 유형 :
다이나믹 프로그래밍- 시간 제한 :
2초
💡문제
BOJ 거리는 보도블록 N개가 일렬로 놓여진 형태의 도로이다. 도로의 보도블록은 1번부터 N번까지 번호가 매겨져 있다.
스타트의 집은 1번에 있고, 링크의 집은 N번에 있다. 스타트는 링크를 만나기 위해서 점프해가려고 한다.
BOJ거리의 각 보도블록에는 B, O, J 중에 하나가 쓰여 있다. 1번은 반드시 B이다.
스타트는 점프를 통해서 다른 보도블록으로 이동할 수 있다. 이때, 항상 번호가 증가하는 방향으로 점프를 해야 한다. 만약, 스타트가 현재 있는 곳이 i번이라면, i+1번부터 N번까지로 점프를 할 수 있다. 한 번 k칸 만큼 점프를 하는데 필요한 에너지의 양은 k*k이다.
스타트는 BOJ를 외치면서 링크를 만나러 가려고 한다. 따라서, 스타트는 B, O, J, B, O, J, B, O, J, ... 순서로 보도블록을 밟으면서 점프를 할 것이다.
스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 구하는 프로그램을 작성하시오.
💡입력
첫째 줄에 1 ≤ N ≤ 1,000이 주어진다.
둘째 줄에는 보도블록에 쓰여 있는 글자가 1번부터 순서대로 주어진다.
💡출력
스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다.
💡예제 입력 1
9 BOJBOJBOJ
💡예제 출력 1
8
💡예제 입력 2
9 BOJBOJBOJ
💡예제 출력 2
8
💡예제 입력 3
9 BOJBOJBOJ
💡예제 출력 3
-1
💡예제 입력 4
13 BJBBJOOOJJJJB
💡예제 출력 4
50
💡예제 입력 5
2 BO
💡예제 출력 5
1
💡예제 입력 6
15 BJBOJOJOOJOBOOO
💡예제 출력 6
52
💡문제요약
- 1번 부터 보도블럭 N번 까지 최소 에너지로 이동하는 것
- B → O → J 순서로 이동
💡알고리즘 설계
N: 보도블럭 개수street: 문자열 읽는 배열
- 각 숫자 문자들을 입력받음
- dp 배열을 N만큼 만들어서 초기화 하고 모든 값을 max값으로 설정 → 이는 해당 보도 블록에 도달 할 수 없음을 의미
- dp[0] 설정 → 에너지 소모가 없음을 의미
- dp 배열을 채우는데 i는 현재 위치 그리고 j는 이전 위치를 나타내며 각 조건문을 통해 B → O → J 순이 맞는지 확인하고 맞으면 dp[i] 에 값을 업데이트
- 만약 dp[N - 1] 값이 max값이라면 이는 도달할 수 없으므로 -1 출력 그렇지 않으면 dp[N - 1] 출력
💡작성코드
Javaimport java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); char[] street = br.readLine().toCharArray(); int [] dp = new int[N]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for(int i = 1; i < dp.length; i++) { for (int j = 0; j < i; j++) { if (street[i] == 'O' && street[j] == 'B' && dp[j] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j)); } else if(street[i] == 'J' && street[j] == 'O' && dp[j] != Integer.MAX_VALUE){ dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j)); }else if(street[i] == 'B' && street[j] == 'J' && dp[j] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i], dp[j] + (i-j)*(i-j)); } } }if (dp[N - 1] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(dp[N - 1]); } } }
💡시간복잡도
O(N^2)
💡틀린 이유 or 수정할 부분
어지저찌 통과..
문제가 생각보다 이해하는데 오래걸렸다. 약간 계속 문제만 보다보니 시간을 조금 날린거 같다.
좀 더 간단한 코드로 구현을 다시 해봤다.
💡틀린 부분 수정 or 다른풀이
Javaimport java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); // 보도블록의 개수 N을 입력받습니다. char[] street = br.readLine().toCharArray(); // 각 보도블록에 적힌 문자를 입력받습니다. int[] dp = new int[N]; // 각 보도블록에 도달하는 데 필요한 최소 에너지를 저장할 배열입니다. // dp 배열을 초기화합니다. 최소값을 찾는 문제이므로 매우 큰 값으로 초기화합니다. for (int i = 0; i < N; i++) { dp[i] = Integer.MAX_VALUE; } dp[0] = 0; // 시작점의 에너지 소비량은 0입니다. // 모든 보도블록을 순회하며 dp 배열을 갱신합니다. for (int i = 0; i < N - 1; i++) { for (int j = i + 1; j < N; j++) { if ((street[i] == 'B' && street[j] == 'O') || (street[i] == 'O' && street[j] == 'J') || (street[i] == 'J' && street[j] == 'B')) { if (dp[i] != Integer.MAX_VALUE) { int energy = (j - i) * (j - i); // i에서 j로 점프할 때 필요한 에너지를 계산합니다. dp[j] = Math.min(dp[j], dp[i] + energy); // 최소 에너지를 갱신합니다. } } } } // 결과 출력: N번 보도블록에 도달하는 데 필요한 최소 에너지. 도달할 수 없는 경우 -1을 출력합니다. if (dp[N - 1] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(dp[N - 1]); } } }
💡느낀점 or 기억할 정보
처음 문제를 풀어도 DP 알고리즘은 무엇이 알고리즘인지 이해가 안 가서 이게 뭔가 싶었다. 근데 DP는 bfs dfs처럼 정해져 있는거 보다는 뭔가 여러방면으로 많이 쓰이는거 같아서 외우다는 개념보다는 뭔가 더 많이 문제를 풀어보고 내 것으로 만들어야 겠다는 생각이 들었다.
