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);
이 됩니다.
웹서핑 하다 저도 재밌는 글을 보게 되어서 여기까지 왔습니다. ^^;;
소스 보고 한수 배우고 갑니다..^^
그런데 얼핏 보니 작성하신 프로그램은 결과의 마지막이 21이라는 것을 알고 있을때의 프로그램인것 같습니다.
잘 오셨습니다. 🙂
그렇습니다. 21이라는 것을 알고 있을때의 프로그램이지요. 🙂 프로그래밍문제는 프로그램문제에만 집중해서 푸는 것이 저의 원칙이라서 그렇습니다. 🙂 물론 문제가 만일 21이 아니고 어떤 수도 가능하게 하자 라고 했으면, 아마 프로그래밍이 달랐을 것 같습니다. 🙂
즐거운 하루 되시고, 새해 복 많이 받으세요. 😉
하성국님의 얘기도 있고, 또 General 하는 프로그래밍이 사실 필요한 듯 하여, Update 했습니다.
우와 웹서핑하다 좋은 자료 보고 갑니다~
요런거 많이 찾고 있었는데 도움 많이 됩니다~! 감사해요~!
네, 감사합니다.