[99클럽] 백준 31926 밤양갱

문제 링크

문제

• daldidalgo를 N번 반복하고 마지막에 daldidan을 입력하여 완성하는 최소 시간을 구하여라.
  • 매초마다 알파벳을 추가하거나 기존 문자열의 연속 부분을 복사해 붙여넣을 수 있다.
  • N의 최대 값은 10^9 (10억)이다.

최종 코드

public class Main {
	public static void main(String[] args) throws Exception {
        int N = read();
        int time = 10;
        int v = 2;
        
        while (v <= N) {
        	v *= 2;
        	time++;
        }
        
        System.out.println(time);
    }
	
	private static int read() throws Exception {
		int c, n = System.in.read() & 15;
		while ((c = System.in.read()) > 32)
			n = (n << 3) + (n << 1) + (c & 15);
		return n;
	}
}

배운점

그리디 알고리즘 익숙해지기

최적의 선택 : 가능한 한 가장 큰 구간을 복사-붙여넣기하기.

• 최초 작업
  • time을 10으로 설정해 시작 시 필요한 시간을 기본적으로 10초로 가정
• 반복적으로 두 배씩 증가
  • v가 N을 넘지 않는 한, 계속 v *= 2로 구간을 두 배씩 증가시키고 time을 1씩 더한다.

이러한 최적의 선택을 도출하기 위해 N이 1 ~ 10일 때 어떤식으로 결과를 계산하게 되는지 손수 작성해봤다(이 문서 최하단 참고).

그러니 규칙이 보였다.

만약 N이 6이라면,

4 < 6 < 8 (2^2 < 6 < 2^3) 일 것이다.

그러면,

• 임의 값(v)가 N보다 커지기 전 까지 반복하면서
  • v가 8보다 작을 때에만 반복
• 임의 값(v)에 2를 곱해가면서 누적시키고
  • v는 2 -> 4 -> 8 순서대로 2 제곱이 됨
• baseTime 10에 1씩 더해주기
  • 10 -> 11 -> 12

위와 같은 연산을 수행하면 된다.

이때,
v는 2부터 시작
time은 10부터 시작하는 것이 포인트이다.

그래야 N에 1이 들어왔을 때 while문에서 반복을 하지 않고, 바로 10을 출력할 수 있다.

여담,
처음에 손으로 써보면서 규칙을 찾을 때 계산을 잘 못했는데, 그 상태로 로직을 구현했더니 계속해서 오답이 나왔다.
답답하여 해답을 한 번 찾아봤는데 비트 연산으로 풀어낸 것을 발견해서, 이런 해답이 아니라 내가 시험장에서도 직접 풀어낼 수 있는 수준으로 풀어봐야한다는 생각에 다시 처음부터 풀어내었고, 결과적으로 답을 찾을 수 있었다.

Kotlin code

import java.io.StreamTokenizer

fun main() = with(StreamTokenizer(System.`in`.bufferedReader())) {
    fun read() : Int {
        nextToken()
        return nval.toInt()
    }

    val N = read()
    var time = 10
    var v = 2

    while (v <= N) {
        v *= 2
        time++
    }

    println(time)
}

---

/*
* n = 1 -> daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldida
* n
* ==> 10
* 
* n = 2 -> daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldida
* n
* ==> 11
* 
* n = 3 -> daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo daldida
* n
* ==> 11
* 
* n = 4 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* daldida
* n
* ==> 12
* 
* n = 5 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* dalgidalgo daldida
* n
* ==> 12
* 
* n = 6 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* dalgidalgo dalgidalgo daldida
* n
* ==> 12
* 
* n = 7 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* daldidalgo daldidalgo daldidalgo daldida
* n
* ==> 12
* 
* n = 8 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* daldidalgo daldidalgo daldidalgo daldidalgo
* daldida
* n
* ==> 13
* 
* n = 9 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* daldidalgo daldidalgo daldidalgo daldidalgo
* daldidalgo daldida
* n
* ==> 13
* 
* n = 10 -> daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan
* d
* a
* l
* d
* i
* dal
* g
* o
* daldidalgo
* daldidalgo dalgidalgo
* daldidalgo daldidalgo daldidalgo daldidalgo
* daldidalgo daldidalgo daldida
* n
* ==> 13
*/