백준 돌림판 문자열

문제

내가 생각했을때 문제에서 원하는부분

첫 번째 줄에 돌림판에 적힌 알파벳 소문자의 개수 N이 주어진다.
두 번째 줄에 돌림판에 적힌 알파벳 소문자 N개가 공백 없이 시계 방향 순서대로 주어진다.
돌림판은 처음에 마지막으로 입력된 문자를 가리키고 있다.
세 번째 줄에 만들어야 하는 문자열 S의 길이 M이 주어진다.
네 번째 줄에 길이가 M인 문자열 S가 주어진다.

돌림판 문자열을 문자열 S로 만들기 위해 필요한 돌림판 회전 수의 최솟값을 출력한다.
돌림판 문자열을 문자열 S로 만들 수 없다면 -1을 출력한다.

내가 이 문제를 보고 생각해본 부분

입력 처리와 초기 변환
BufferedReader로 표준 입력을 읽는다.
첫 줄에서 정수 N(돌림판 길이)을 읽고, 둘째 줄에서 돌림판에 적힌 문자열 dial을 읽는다.
셋째 줄에서 정수 M(만들어야 할 문자열 길이)을 읽고, 넷째 줄에서 목표 문자열 S를 읽는다.
dial을 char 배열로 변환해 인덱스 접근을 쉽게 한다(dialChars).
DP 배열 정의 및 초기화
dp[i][j]는 "S의 i글자(0..i-1)를 이미 만든 상태에서 돌림판 포인터가 인덱스 j를 가리키고 있을 때의 최소 누적 회전 수"를 의미한다.
dp 크기는 (M+1) x N이며, 모든 칸을 큰 값(Integer.MAX_VALUE/2)으로 초기화해 도달 불가 표시로 사용한다.
시작 상태: 아무 문자도 만들지 않았고(즉 i=0), 돌림판 포인터는 마지막 문자 인덱스 N-1을 가리키므로 dp[0][N-1] = 0으로 설정한다.
상태 전이(중첩 루프 구조)
외부 루프 i = 0 .. M (만든 글자 수)
내부 루프 pos = 0 .. N-1 (현재 포인터 위치)
만약 dp[i][pos]가 무한값이면 건너뛴다(도달 불가 상태).
curCost = dp[i][pos]를 현재 누적 비용으로 가져온다.
rot = 1 .. N 범위로 모든 가능한 회전량을 시도한다.
nextPos = (pos + rot) % N 으로 회전 후 위치를 계산한다.
회전만 하는 전이(문자 추가 없음): dp[i][nextPos] = min(dp[i][nextPos], curCost + rot)
같은 i(만들어낸 글자 수 유지) 상태에서 포인터만 옮기고 비용만 누적하는 경우이다.
회전 후 돌림판 문자와 S의 다음 문자(i번째, 0-based)가 같다면 문자 추가 전이를 수행: dp[i+1][nextPos] = min(dp[i+1][nextPos], curCost + rot)
즉, 회전으로 해당 위치로 포인터를 옮기고 그 문자를 사용(consume)하면 만든 글자 수가 하나 증가한다.
결과 도출
모든 글자 M을 만든 상태(dp[M][j], j=0..N-1)들 중 최소값을 찾아 answer에 저장한다.
만약 최소값이 여전히 무한값이면 도달 불가로 -1을 출력하고, 그렇지 않으면 그 최소 회전 수를 출력한다.
마지막으로 BufferedReader를 닫아 자원을 해제한다.

코드로 구현

package baekjoon.baekjoon_32;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

// 백준 25705번 문제
public class Main1282 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        String dial = br.readLine();
        int M = Integer.parseInt(br.readLine());
        String S = br.readLine();

        char[] dialChars = dial.toCharArray();

        // dp[i][j] = S의 i글자까지 만들고 돌림판이 j 위치를 가리킬 때 최소 회전 수
        int[][] dp = new int[M + 1][N];
        for (int[] row : dp) {
            Arrays.fill(row, Integer.MAX_VALUE / 2);
        }
        // 처음엔 아무 문자도 만들지 않았고 돌림판은 마지막 문자 가리킴
        dp[0][N - 1] = 0;

        for (int i = 0; i <= M; i++) {
            for (int pos = 0; pos < N; pos++) {
                if (dp[i][pos] == Integer.MAX_VALUE / 2) continue;

                int curCost = dp[i][pos];

                for (int rot = 1; rot <= N; rot++) {
                    int nextPos = (pos + rot) % N;

                    // 회전만 했을 때 (문자열 추가 안함)
                    if (dp[i][nextPos] > curCost + rot) {
                        dp[i][nextPos] = curCost + rot;
                    }
                    // 회전 후 돌림판 문자가 S의 다음 문자와 같으면 추가
                    if (i < M && dialChars[nextPos] == S.charAt(i)) {
                        if (dp[i + 1][nextPos] > curCost + rot) {
                            dp[i + 1][nextPos] = curCost + rot;
                        }
                    }
                }
            }
        }

        int answer = Integer.MAX_VALUE;
        for (int j = 0; j < N; j++) {
            answer = Math.min(answer, dp[M][j]);
        }

        System.out.println(answer == Integer.MAX_VALUE / 2 ? -1 : answer);
        br.close();
    }
}

미무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.