CF R #695_A 복습

A. Wizard of Orz

문제 설명

0~9 중 하나의 숫자를 표현할 수 있는 패널 n개가 왼쪽에서 오른쪽으로 일렬로 놓여있다. 모든 패널은 동시에 0부터 시작하며, 모두 매 초마다 1씩 숫자가 증가한다. 숫자가 9인경우에는 증가하지 않고 다시 0으로 돌아간다.
사용자는 n개의 패널중 하나만을 골라 원하는 때에 멈출 수 있다. 멈춘 패널은 숫자의 변화가 즉시 멈추지만 인접한 패널은 1초 후에 멈추게 되며 2칸이 떨어진 패널은 2초후에, k칸이 떨어진 패널은 k초 후에 멈추게 된다.
예를 들어 4개의 패널이 9999를 가르킬 때 왼쪽에서 두번째 패널을 멈춘 경우 9999 -> 0900 -> 0901 순서로 변화하여 모든 패널이 멈추게 된다.
모든 패널이 멈추었을 때 왼쪽부터 오른쪽으로 숫자를 차례대로 이어붙여 하나의 수를 만들 수 있다. 패널의 개수 n이 주어졌을 때 모든 패널이 멈추었을 때 나올 수 있는 가장 큰 수를 구하시오.

예시

입력

2

출력

98

나의 풀이과정

가장 큰 수가 나오려면?

하나의 패널을 고르면 나머지 패널이 1씩 증가하는 모습으로 쭉 반복된다는 점. 그리고 가장 큰 숫자가 되기 위해서는 가장 왼쪽의 수가 9가 되어야 한다는 점은 직관적으로 알 수 있었다.

왜 왼쪽 끝 수가 9가 되어야 하는가?

사용자는 어느 순간에나 패널을 고를 수 있으므로 맨 왼쪽이 9가 나오도록 선택하는 것이 항상 가능하다. 만약 왼쪽 끝 수가 9가 아니라면 9인 경우보다 항상 작으므로 정답이 될 수 없다. 따라서 제일 왼쪽 끝 수는 9가 되어야 한다.

제출 1

for (int i=0,n; i < t; i++){
   cin >> n;
   for(int j=0,k=9; j<n; j++){
       cout << k;
       k = (k+9)%10;
   }
cout << endl;

왼쪽 끝이 9이면서 한칸마다 1씩 차이가 나므로 9876543210987... 순으로 출력하면 답일 것이라 생각하였으나 오답이었다.

제출 2

int add = -1;
cin >> n;
for(int j = 9,id=0; id < n; id++){
     cout << j;
     if( (j==0) && (add==-1) ) add = 1;            
     j = (j+add)%10;
  }
cout << endl;  

98765432101234567890... 순으로 출력되도록 하였다. 제출1보다 더 작은 수가 나오는 코드인데 깊게 생각하지 않고 제출한 코드같다. 이렇게 생각한 이유도 대강 짐작은 간다. 첫번째로 제출한 코드의 답이 숫자가 양쪽으로 한칸씩 늦게 멈춘다는 조건을 빼먹었기 때문에 틀렸다고 생각해서 그런 것 같다. 그 생각과는 달리 첫번째 코드는 문제의 전제조건에 맞는 출력값이다. 맨 마지막 패널을 멈추면 제출1의 숫자패턴을 만들 수 있기 때문이다. 다만 최대값이 아닐 뿐이었다.
이 이후로도 비슷한 오답을 반복하였다.

가장 큰 수가 나오려면? 2

문제를 다시 생각해 보았다. 제일 왼쪽수는 분명 9가 되어야 하는데 n이 5인경우에는 98765가 가장 큰가? 98767도 만들 수 있는것 같다. 어? 그럼 98789도 만들수 있겠네? 아하 989012345... 가 가장 큰 수의 패턴이겠구나.

제출 3

cin >> n;
if (n == 1) {cout << 9 << endl; continue;}
if (n == 2) cout << 98 << endl;
else{
  cout << 98;
  for(int j=0,base=9; j<n-2; j++){
      cout << base;
      base = (base+1)%10;
  }
  cout << endl;
}

느낀 점

쉬운 문제라고 생각하고 깊게 생각하지 않았더니 여러번 오답을 제출하게 되었다. 한번 잘못된 생각을 갖고 나니, 실제 예시를 생각해보면 금방 찾을 수 있는 맹점을 찾지 못한 것 같다. 문제를 풀 때는 쉬워보이는 문제도 실례를 적어가며 푸는 것이 좋겠다.