[Day17]JAVA 백준 밤양갱(31926번)

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

 

 

---

백준 31926번 밤양갱 문제를 풀기 위해서는 규칙(Greedy)을 파악해야 한다.

 

그리디 문제는 규칙을 파악하는게 중요한데 쉬워보일 수록 꼼꼼하게 따져봐야 한다... 놓치는 부분이 발생할 수 있기다..

 

밤양갱의 주요 규칙은

• 지금까지 입력한 문자열의 연속된 부분 분자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다.

기본인 daldidalgo 단어만 본다면 한 문자씩 입력을 하다가 dal 부분에 붙여넣기가 가능하다. 붙여넣기는 1초 걸린다고 하면  daldidalgo 를 입력하기 까지 총 8초가 걸린다. 

 

daldidan 단어는 daldida 까지 붙여넣기가 가능하므로 마지막 n 만 입력하면 총 (8+1+1)9초가 걸린다.

 

---

좀 더 심화 학습 가겠다.

N 이 7 일 때는 daldida 까지 복붙을 하여서 마지막 n 만 입력 하여 1초를 더하여 총 12 초가 걸린다.

• 기본 8초 + 복붙 3초 + n 1초 = 12초

 

 

N 이 8 일때는 daldida 은 붙여넣고 n은 입력하여 2초를 더하여 총 13 초가 걸린다.

• 기본 8초 + 복붙 3초 + 복붙1초 + n1초 = 13ch 

 

2가지 경우를 확인 할 수 있다. 

• 마지막 daldida 까지 한번에 붙여 넣기가 되어서 마지막 n만 입력 하면 되는 경우 ->  +1 더해주면 된다.
• 마지막 dadida 와 n 을 따로 처리해야하는 경우 를 구분해서 붙여넣기를 하는 것이다.  > +2 더해주면된다.

 

---

위의 규칠을 활용하여 코드를 짜보면 3가지 경우를 대비하여 작성하면 된다. 

• count : 현재까지 입력된 daldidalgo 의 횟수 
• N :  최종 입력하고자 하는 횟수
• answer : 소요된 시간

1. 붙여넣기를 하면서 지금까지의 전체 횟수를 붙여넣기(count *2)  할때 총 횟수(N)를 벗어나지 않으면 계속 붙여넣기를 진행
2. 지금까지 의 전체 횟수 (count *2)  를 붙여넣기 하면 총 횟수(N) 와 동일하면 마지막 daldidan 을 처리하면 +2 
3. 지금까지 의 전체 횟수 (count *2)  를 붙여넣기 하면 총 횟수(N) 를 넘어서면 마지막 n만 입력하여  처리하면 +1

 

*최종코드

import java.io.*;
public class Main{
    public static void main(String[] args) throws IOException
    {        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        long count = 1; 
        int answer =8; //처음 daldidalgo 입력하기에 8초 소요
        
        // 횟수
        long n = Long.parseLong(br.readLine());

        if(n ==1)
        {
            System.out.println(answer + 2);
            return;
        }

        while(n>1)
        {
            if(count*2 <n)
            {                
                answer++;
                count = count*2;
            }
            else if(count*2 == n)
            {
                //daldida 과 n 을 각각 입력 해야하는 경우
                answer++;
                answer = answer +2;
                break;

            }          
            else
            {
                //daldida 까지 붙여넣기 하고 n만 입력 해야하는 경우
                answer++;
                answer = answer +1;
                break;
            }

        }
        
        System.out.println(answer);
    }   
}