C 언어 문제

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);

이 됩니다.

You May Also Like

5 Comments

  1. 웹서핑 하다 저도 재밌는 글을 보게 되어서 여기까지 왔습니다. ^^;;
    소스 보고 한수 배우고 갑니다..^^
    그런데 얼핏 보니 작성하신 프로그램은 결과의 마지막이 21이라는 것을 알고 있을때의 프로그램인것 같습니다.

    1. 잘 오셨습니다. 🙂

      그렇습니다. 21이라는 것을 알고 있을때의 프로그램이지요. 🙂 프로그래밍문제는 프로그램문제에만 집중해서 푸는 것이 저의 원칙이라서 그렇습니다. 🙂 물론 문제가 만일 21이 아니고 어떤 수도 가능하게 하자 라고 했으면, 아마 프로그래밍이 달랐을 것 같습니다. 🙂

      즐거운 하루 되시고, 새해 복 많이 받으세요. 😉

  2. 하성국님의 얘기도 있고, 또 General 하는 프로그래밍이 사실 필요한 듯 하여, Update 했습니다.

  3. 우와 웹서핑하다 좋은 자료 보고 갑니다~
    요런거 많이 찾고 있었는데 도움 많이 됩니다~! 감사해요~!

답글 남기기

이메일 주소는 공개되지 않습니다. 필수 필드는 *로 표시됩니다