[자바] 백준 1515번: 수 이어 쓰기

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

1515번: 수 이어 쓰기

실버3인데 생각보다 어렵게 푼 문제.

dp로 풀었다.

2번을 위해 1번에서 문자열 포함여부를 확인할 때 indexOf 메소드를 이용하였다.

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

public class P1515 {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		String str = br.readLine();
		int[] dp = new int[str.length() + 1];
		for (int i = 0; i < str.length() + 1; i++) {
			dp[i] = 0;
		}
		dp[0] = 0;

		for (int i = 0; i < str.length(); i++) {
			String now = String.valueOf(str.charAt(i));
			if (dp[i + 1] != 0)
				continue;
			int min = dp[i] + 1; // 이번 숫자 최솟값

			while (true) {
				String compareNum = String.valueOf(min);
				int idx = -1;
				if ((idx = compareNum.indexOf(now)) != -1) {
					dp[i + 1] = min;
					// 최솟값 찾았으니 다음수도 포함됐는지 확인
					for (int j = i + 1; j < str.length(); j++) {
						String next = String.valueOf(str.charAt(j));
						if (++idx >= compareNum.length())
							break;
						idx = compareNum.indexOf(next, idx);
						if (idx == -1)
							break;

						dp[j + 1] = min;

					}
					break;
				} else {
					min++;
				}
			}

		}

		System.out.println(dp[str.length()]);
	}

}