백준 31926번 밤양갱 - C++

문제

---

 

달디달고, 달디달고, 달디단, 밤양갱, 밤양갱

<장기하, 밤양갱, 2024>

민우는 비비의 신곡 <밤양갱>에 꽂혀 하루 종일 "달디달고 달디달고 달디달고... 달디단"이 머릿속을 맴돌고 있다.

민우의 머릿속에선 daldidalgo가 총 N$N$번 반복된 후, 반복이 완료되었다면 daldidan으로 끝나게 된다. 예를 들어 N=3$N=3$이라면 민우의 머릿속엔 daldidalgodaldidalgodaldidalgodaldidan이 재생된다.

민우는 N$N$이 주어지면 얼마나 빨리 daldidalgodaldidalgo...daldidan을 컴퓨터에 입력할 수 있는지 궁금하다. 매초 민우는 두 개의 작업 중 하나를 선택하여 시행할 수 있다.

• 알파벳 소문자 a부터 z 중에서 민우가 원하는 알파벳을 하나 골라서 지금까지 입력한 내용의 맨 뒤에 입력한다.
• 지금까지 입력한 문자열의 연속된 부분 문자열을 복사 후 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면, ajouapcshake를 복사할 수도, apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.

민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?

 

입력

첫 번째 줄에 민우의 머릿속에 떠오른 daldidalgo의 횟수 N$N$이 주어진다. (1≤N≤109)$(1\leq N \leq 10^9)$ 

 

출력

민우가 문제에 언급된 시행 중 하나를 선택하여 매초 시행했을 때, N$N$번의 daldidalgo를 입력한 후 1$1$번의 daldidan을 입력할 수 있는 최소 시간을 출력한다.

 

문제 링크

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

 

 

풀이

---

처음 `daldidalgo`까지 입력하는데는 8만큼 걸리게 된다.

그러나 그 다음부터는 처음 입력한 `daldidalgo`를 복사하면 되므로 추가적으로 걸리는 시간은 1이다.

하지만 `daldidan`을 만드는 시간이 2가 소모된다.

 

하지만 N이 홀수인 경우, 마지막 부분을 복사를 할 때 앞의 $N / 2 + 1$번 반복된 `daldidalgo`까지 만든다음, $N / 2$ 번 반복된 `daldidalgo`에 `daldida`까지 복사해서 넘겨주면 뒤의 `daldidan`을 만드는데는 1이 걸리게 된다.

그러나 결국에는 홀수의 경우 $N / 2 + 1$개 까지는 만들어야 마지막 `daldidan`을 만드는데 걸리는 시간이 1로 줄어드는 것이기에 이러나 저러나 $log(N) + 2$가 된다.

 

 

C++ 코드

---

#include <iostream>

using namespace std;

long long N;
long long answer;

void input() {
  cin >> N;
}

void solve() {
  while (N > 1) {
    N /= 2;
    answer ++;
  }
}

void output() {
  cout << answer + 10;
}


int main() {
  input();
  solve();
  output();
}