suakiis log님의 블로그를 보다가 재미있는 문제가 있어 여기에 퍼옵니다.

문제:

자 C언어 아니 다른 언어여도 좋다.
while 2개, 변수 2개로 다음과 같은 결과를 나오도록 해보자.

1    2   3  4  5
6    7   8  9
11 12 13
16 17
21

이 문제에 대한 답으로 저는 변수는 두개 썼지만, while문은 하나만 써서 O(n^2)에서 O(n)으로 만들었습니다.

다음은 제가 만든 코드입니다.

#include <stdio.h>

int main(void) {
  int a = 1;
  int b = 6;
  while (a < 22) {
    if (a < b) {
      printf("%02d  ", a);
    }
    if (!((a++)%5)) {
      printf("n");
      b=5+(--b);
    }
  }
  printf("n");
}

Update:

만일 k 값에 따라서 출력되는 것을 다르게 하는 일반화를 하면 다음과 같이 나올 것입니다.

#include <stdio.h>

int main(void) {
  int a = 1;
  int k = 5;
  while (a <= k*k) {
    if (!(a > k+((a-1)/k)*(k-1))) printf("%02d ", a);
    if (!(a%k)) printf("n");
    a++;
  }
  return 1;
}

위와 같이 될 수 있는 이유는 간단하게 수학을 했기 때문입니다. 생각해보면, Width (K) 와 Index (i) 와 계속에서 출력해 내는 변수인 (A) 가 필요합니다. 그런데, Index의 경우는 간단한 수학으로 K 와 A를 이용하여 구할 수 있습니다. 위에서는 그 Index의 계산식을 이용하여 Index에 필요한 변수를 없앴을 뿐입니다.

즉,

--- k=4 ---
01 02 03 04   : i=0
05 06 07 (8)  : i=1
09 10(11)(12) : i=2
13(14)(15)(16): i=3

A가 1 부터 16 (K*K)까지 변할때까지 무조건 출력하면 됩니다. 다만, A가 8, 12, 16 과 같이 K의 배수가 되는 순간에는 Line Feed를 출력하여 다음 행으로 출력하게 합니다.

또한, 출력되는 행에서 A가 (1+i)*k-i 보다 크면 출력하지 않게 합니다. 여기서 i=(a-1)/k 가 됩니다. 즉,

if (a > (i+1)*k-i) 이면 출력하지 않음

이 됩니다. 그러면, 계산에서 i의 반복사용을 줄이기 위해 바꾸면, k+i*(k-1) 이 되고, i=(a-1)k 를 대입하면

if (!(a > k+((a-1)/k)*(k-1))) printf("%02d ", a);

이 됩니다.