99클럽 코테 스터디 17일차 TIL : 그리디 알고리즘(백준 31926번 밤양갱)

 

 

 

 

 

 

 

 

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

 

 

 

---

🔎 문제 

N = 1
daldidal 6개
daldidalgo 8개
daldidalgo daldidan 10개

N = 2 
daldidal 6개
daldidalgo 8개
daldidalgo daldidalgo 9개
daldidalgo daldidalgo dandidan 11개

N = 3
daldidalgo daldidalgo 9개
daldidalgo daldidalgo daldidalgo dandida 10개
daldidalgo daldidalgo daldidalgo dandidan 11개

N= 4
daldidalgo daldidalgo 9개
daldidalgo daldidalgo daldidalgo daldidalgo 10개
daldidalgo daldidalgo daldidalgo daldidalgo daldidan 12개

N =  5
daldidalgo daldidalgo 9개
daldidalgo daldidalgo daldidalgo daldidalgo 10개
daldidalgo daldidalgo daldidalgo daldidalgo daldidalgo daldidan 12개

N = 6 12개
N= 7  12개
N = 8 13개

...

N=15 13개

N = 16 14개
...

 

=>  N = 2^n 수를 지날 때마다 1개씩 추가됨 

 

 

💡 풀이

- cnt: 현재 문자를 만드는데 걸린 수 (default : daldidalgo 한개 만드는 데 걸린 횟수 8번)

- su: 현재 daldidalgo 개수 (default : 1개)

- N+1 까지 반복해주는 이유는 daldidalgo 갯수가 N개이고 그 뒤에 daldidan 이 한번더 있기 때문에 N+1개를 붙인다고 생각함(daldidan에서 daldida 까지만 복사)

- 그 후 'n' 글자를 한번 더붙이기 때문에 cnt+1로 출력

 

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

public class Main {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int cnt = 8;
		int su = 1;
		
		for(int i=2;i<n+2;i++) {
			if(su<i) {
				su = 2*su; 
				cnt++; 
			}
		}
		
		System.out.println(cnt+1);

	}

}

 

 

 

📌 오늘의 회고

현재까지 단어개수만큼 복사붙여넣기한다 가정하면 2의 제곱수를 기준으로 1번씩 추가된다는 것을 찾아서 쉽게 해결 할 수 있었다 !