백준 31926번 : 밤양갱(실버 1)

백준 31926번

오늘의 미들러 문제인 밤양갱 문제이다. 비비의 "달디달고 달디단 밤양갱"에서 영감을 받은 문제인 것 같다

문제에서 N이 주어지고 N만큼 "daldidalgo"를 입력하고 마지막으로 "daldidan"을 입력하는 문제이다

그래서 원래 같았으면 문자를 하나씩 입력할 때마다 1초씩 걸리는데 여기서 치트키로 지금까지 작성한 문자열 중 연속된 부분 문자열을 복사해서 붙여넣을 수 있다

풀이

일단 가장 처음에 "daldidalgo"를 입력하는 데는 몇 초가 걸릴까?

"daldi"를 입력할 때까지는 앞에 중복되는 문자열이 없으므로 일일이 다 쳐야 한다. 그래서 5초가 걸린다

그 다음 "dal"이 앞에 연속적으로 있으므로 그대로 복사하면 되니까 1초가 걸린다

그리고 "go"는 앞에 없으므로 다 쳐준다. 2초가 걸린다

그래서 처음 "daldidalgo"는 8초가 걸린다

그리고 "daldidan"은 "daldidalgo"에서 "daldida"까지 복사할 수 있으므로 1초 + n 입력 1초 = 2초가 걸린다

그래서 N이 1이라면 총 10초가 걸린다

N이 2일때는 어떨까?
"daldidalgo"를 처음 한 번 입력하고(8초) 그대로 복붙하고(1초) "daldidan"을 입력한다(2초)
총 11초가 걸린다

N이 3일때는
("daldidalgo", 8초)("daldidalgo", 1초)("daldidalgodaldida", 1초)("n", 1초)
총 11초

N이 4일때는
("daldidalgo", 8초)("daldidalgo", 1초)("daldidalgo", 1초)("daldidalgodaldida", 1초)("n", 1초)
총 12초

N이 7일때는
("daldidalgo", 8초)("daldidalgo", 1초)("daldidalgodaldidalgo", 1초)("daldidalgodaldidalgodaldidalgodaldida", 1초)("n", 1초)
총 12초

N이 8일때는
("daldidalgo", 8초)("daldidalgo", 1초)("daldidalgo", 1초)("daldidalgodaldidalgo", 1초)("daldidalgodaldidalgodaldidalgodaldida", 1초)("n", 1초)
총 13초

...

규칙을 찾아보면 N이 2의 제곱수(1, 2, 4, 8 ...)일 때마다 1씩 커진다. 이를 코드로 나타내면 정답을 나타내는 second 변수를 처음에 10으로 초기화하고 1부터 시작해서 제곱씩 커질때마다 second를 1씩 증가시킨다

코드

#include <bits/stdc++.h>
using namespace std;

int N;

void Input()
{
    cin >> N;
}

void Solve()
{
    int second = 10;

    int idx = 1;
    while (N >= pow(2, idx++))
    {
        second++;
    }

    cout << second;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    Input();

    Solve();

    return 0;
}

회고

처음 문제를 풀었을 때 규칙은 어느정도 찾았는데 코드로 옮겨내는 과정이 좀 시간이 많이 걸렸다. 마지막 "daldidan"이 "daldidalgo"가 두 번 이상 나왔을 때 복붙할 수 있다는 점을 생각해내면 좋을 듯