[백준 1515] 수 이어 쓰기 - JAVA

BOJ Link

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

 

 

 

 

 

 

풀이 과정

문자열의 길이는 3천 이하이므로, 그리디만 적용하면 널널하게 탐색할 수 있어서 매 탐색마다 int to string 변환을 했다.

 

1. 현재 숫자 num으로 문자열의 부분을 구성할 수 있을 때, 더 큰 숫자로 구성하는게 최적인 경우는 없다 => 그리디

e.g. 112 같은 경우, 무조건 작은 수 부터 (1 -> 12) 이루는게 최적이다. 더 큰 수(11 -> 12)는 잘해봤자 같은 값이다.

 

1-1. 탐색의 시작은 0번째 인덱스에 쓰인 num부터 진행한다. ( 또한 숫자가 0인 경우, 가장 작은 숫자는 10이다.)

1-2. 이후 num을 1씩 올려가며 문자열의 부분을 구성할 수 있다면 항상 최적이다.

 

2. 현재 num에 목표로하는 숫자 goal이 포함된다면, 이후엔 뒤의 숫자가 num이 끝날 때 까지 포함되는지 확인해야 한다.

e.g. 111 같은 경우, (1 -> 11 -> 12)가 아닌 (1 -> 11)로 구성할 수 있다.

 

2-1. goal을 찾은 이후, 일치하는 숫자가 연속되지 않은 경우 또한 마찬가지이다.

e.g. 0000000000113은 (100 -> 101 -> 110 -> 113)이 아닌, (100 -> 101 -> 103)으로 이룰 수 있다. 00000000001103 과 같은 꼴로 취급할 수 있기 때문이다.

 

 

2-1번을 찾는데 좀 걸렸고, 문제 분류엔 없지만 이분 탐색으로 또한 풀이가 가능하다.

이유는, 어떤 수가 해가 아니라면 수를 늘려야하고, 해라면 수를 줄여야 함이 보장되기 때문이다.

제출 코드

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

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s = br.readLine();

        char sc = s.charAt(0);
        int start = sc == '0' ? 10 : (int) sc - '0';
        int idx = 1;
        int num = start;

        while (idx < s.length()) {
            int goal = s.charAt(idx) - '0';

            String snum = String.valueOf(++num);

            for (int i = 0; i < snum.length(); i++) {
                if (snum.charAt(i) - '0' == goal) {
                    idx++;

                    if (idx == s.length()) break;
                    goal = s.charAt(idx) - '0';
                }
            }

        }

        System.out.println(num);
    }
}