99클럽 코테 스터디 17일차 TIL (31926번: 밤양갱)

문제

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

---

학습 키워드

• 그리

 

풀이 및 코드

최초로 daldidalgo를 만드는데 필요한 시간은 8초이다.

1. d
2. da
3. dal
4. dald
5. daldi
6. daldidal (dal 복사-붙여넣기)
7. daldidalg
8. daldidalgo

그 다음에는 daldidalgo를 N - 1번 붙여넣기를 하는데 가능하면 daldida를 포함하여 붙여넣기를 해야 최소 시간이 나온다.

• N=2일 때,
  1. daldidalgo(8초)
  2. daldidalgodaldidalgo(9초. daldidalgo 복사-붙여넣기)
  3. daldidalgodaldidalgodaldida(10초. daldida 복사-붙여넣기)
  4. daldidalgodaldidalgodaldidan (11초. n 추가)
• N=3일 때,
  1. daldidalgo(8초)
  2. daldidalgodaldidalgo(9초. daldidalgo 복사-붙여넣기)
  3. daldidalgodaldidalgodaldidalgodaldida(10초. daldidalgodaldida 복사-붙여넣기)
  4. daldidalgodaldidalgodaldidalgodaldidan (11초. n 추가)

 이걸 그림으로 표현하면 아래와 같이 나온다.

N=2 일 때는 8 + 1 + 2 = 11

N=3일 때는 8 + 1 + 2 = 11

N=4일 때는 8 + 2 + 2 = 12

.

.

.

N=8일 때는 8 + 3 + 2 = 13

 

즉, 처음 daldidalgo 와 마지막 daldidan을 제외한 사이의 개수는 N의 log2 값이 되므로 8 + log2(N) + 2를 하면 정답이 된다.

import java.util.*;

public class Main {
    public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);

       int N = sc.nextInt();
       System.out.println(8 + log2(N) + 2);
    }

    private static int log2(int n) {
       return (int)(Math.log(n) / Math.log(2));
    }
}