99클럽 코테 스터디 17일차 TIL 그리디(밤양갱)

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

<아이디어>

요 문제를 통해 '애드 혹'에 대해 찾아봤다. 애드 혹은 특정 상황에서만 정답이 되고 일반화될 수 없는 것을 의미한다. (cf.달디달고 달디단)

처음엔 그리디 문제 같아서 입력크기 잘 안봤다가 디피로 만들어서 메모리가 터졌다.

그리고는 규칙을 찾으려고 주석에 분석했는데 (요런 문제가 헷갈려서 더 어려운 거 같다 ㅠ)

앞 달디달고는 무조건 8이 되고, 뒤 달디단은 홀수 짝수 인 경우에 조금은 달라지긴 하지만 결국 2가 된다는 것을 알 수 있다.

그리고 중간의 달디달고는 1, 2, 4, 8 씩 복사를 통해 생성된다는 것을 알 수 있다.

따라서 10은 고정이고, n을 2로 나누면서 반으로 쪼개는 횟수를 더해주면 답이 된다.

 

<제출 코드>

package Study.Week03;

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

/*
* n=1 (daldidalgo) (daldida)(n) => 8 + 2
* n=2 (daldidalgo) (daldidalgo) (daldida)(n) => 8 + /1/ + 2
* n=3 (daldidalgo) (daldidalgo) (daldidalgo daldida)(n) => 8 + 1 + 2
* n=4 (daldidalgo) (daldidalgo) (daldidalgo daldidalgo) (daldida)(n) => 8 + /1 + 1/ + 2
* n=5 (daldidalgo) (daldidalgo) (daldidalgo daldidalgo) (daldidalgo daldida)(n) => 8 + /1 + 1/ + 2
* */

public class Day17_BOJ_31926_밤양갱 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int cnt = 10;
        while(n > 1){
            n /= 2;
            cnt++;
        }
        System.out.println(cnt);
    }
}