[TIL] 99클럽 코테 스터디 17일차 TIL + 백준 31926 밤양갱

 

문제 풀이

 

문제 탐색하기

"daldidalgo" 라는 문자열을 N번 반복하고 마지막에는 "daldidan"을 입력하는 최소시간을 구하는 문제입니다.

문자열을 완성시킬 수 있는 방법은 2가지가 있습니다.

• 알파벳 소문자를 직접 입력
• 원하는 부분의 연속된 문자열을 복사하여 끝부분에 붙이기

 

이 문제에 대한 예시로 N이 17이 주어졌을 때 밤양갱 가사를 완성하는 과정에 대해 설명하도록 하겠습니다.

 

1. 첫 "daldidalgo"를 완성 시키는 방법은 아래와 같습니다. 총 8초가 걸리는 것을 알 수 있습니다.
   • d a l d i : 알파벳 5개를 하나씩 입력
   • 입력된 문자열에서 "dal" 문자를 복사해서 뒤에 붙이기 -> daldidal
   • g o : 알파벳 2개를 추가로 입력
2. 이제 부터는 앞의 문자열을 복사해서 가사를 완성할 수 있습니다. 문자열을 X로 표기하도록 하겠습니다.
   • 1번을 통해 만들어진 X를 복사하여 XX
   • XX -> 전체 복사하여 XXXX (N = 4)
   • XXXX -> 전체 복사하여 XXXXXXXX (N = 8)
   • 이렇게 자신의 2배를 계속 복사하여 N만큼 반복되는 가사를 완성시킬 수 있습니다.
   • XXXXXXXX -> XXXXXXXXXXXXXXXX (N=16)
   • 이제 17번 반복되는 밤양갱 가사를 완성 시키기 위해서는 X만 복사하여 뒤에 추가로 붙이면 됩니다.
3. 여기서 주의해야할 점! 마지막 "daldidan" 문자열도 붙여줘야합니다.
   • N=16 을 만족시킬 때까지 반복하면 총 8 + 4 = 12초가 걸리게 됩니다.
   • N=17을 붙일때 마지막으로 붙여줘야하는 "daldida" 도 함께 붙여주면 됩니다. 즉, 17번째에는 "daldidalgodaldida" 가 붙게 됩니다. 현재 존재하는 문자열에서 원하는 부분을 복사할 수 있기때문에 충분히 가능한 과정입니다.
   • 마지막으로 "n" 까지 붙여주게되면 총 12 + 1 + 1 = 14초가 걸리게 됩니다. 
4. 위 과정을 바탕으로 민우가 해야할 행동에 대해 구분지어 보겠습니다.
   • 첫 "daldidalgo"와 마지막 "n"을 처리하는 9초를 따로 세팅
   • 이제 문자열의 반복 횟수를 1로 지정하고 N을 넘을 때까지 2배를 해주면서 시간을 +1
   • while문이 종료되면 총 걸린 시간 출력

이 문제는 현재의 상황에서 최적의 해답을 내기 위해서 선택을 반복하게 되면 답을 구할 수 있는 그리디 알고리즘을 활용한 문제였습니다.

 

문제 풀이

import java.io.IOException;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();

        int minTime = 9; // d a l d i dal g o / n <-- 첫번째 "daldidalgo", 마지막 "n" 입력하는 카운트

        int strCnt = 1; // daldidalgo 반복 카운트
        while(strCnt <= N){
            minTime++;
            strCnt*=2;
        }

        System.out.println(minTime);
    }
}

 

 

오늘의 회고

문제를 제대로 파악하지 않고서 daldidalgo 문자열만 반복시켜서 답을 구하려고 했는데 알고보니 현재 만들어진 문자열을 계속 2배를 해서 답을 구할 수 있는 문제였습니다. 문제를 파악하는 데에 시간을 적절하게 쓰는 것이 매우 중요하다는 것을 느끼는 시간이었습니다ㅎㅎ.