<Dovelet> 9계단 - 비트패턴

나의 첫 백트래킹 문제..

풀고나서도 완벽하게 코드를 따라가지 못해서 1주일 동안 하루에 한번씩 반복해서 풀었던 기억이 있다..

[이건 그흔적들...]

백트래킹 알고리즘은 재귀함수를 응용해서 모든 경우의 수를 탐색해버리기 때문에 정확성이 굉장히 높다는 장점이 있는데 반면에 모든 경우의 수를 탐색하기 때문에 속도가 느리다는 단점을 가지고 있다고 한다.

자칫했다간 무한루프가 나올 수도 있으니 신중히 생각하면서 코딩하는게 좋다

http://59.23.150.58/30stair/pat/pat.php?pname=pat

두 정수 n , k 를 입력으로 받아 k 개의 1 을 가진 n 자리 이진 패턴을 출력하는 프로그램을 작성 하세요. 입력 두 정수 n , k 가 입력으로 주어진다. (0 < n <= 30 , 0 <= k < 8 , n >= k) 출력 결과를 내림차순으로 출력한다.

#include<stdio.h> int n,k,a[100]; void pat(int x, int y){ int i; if(x>=n){ if(y==k){ for(i=0; i<n; i++)printf("%d",a[i]); printf("\n"); } return; } if(y<k){ a[x]=1; pat(x+1,y+1); } a[x]=0; pat(x+1,y); } int main(void){ scanf("%d %d",&n,&k); pat(0,0); return 0; }