동전 앞면(C++)

동전을 n개 던저서 앞면이 k개 나오는 경우를 모두 출력하여라. n은 최대 20까지 입력되고 앞면이면 "앞" 뒷면이면 "뒤" 으로 출력하라. 출력결과는 한줄에 하나씩 출력하되 "뒤"가 더 앞쪽에나온 순으로 출력하라. 출력 가장 마지막 줄에는 총 경우의 수를 출력하라.




"뒤"가 더 앞쪽에 나오는 순이란 말은 "앞"이 더 뒤쪽에 나오는 순서라는 말과같다.
만약 뒤를 0으로 앞을 1로 본다면, 1의 개수가 같은 것 중에 수가 더 낮은 것 부터 출력하라는 말과 같다.

따라서 다음과 같은 방법을 생각해 볼 수 있다.

이진수로 0부터 1씩 더해가면서 알맞는 1의 갯수가 k 될때만 0과 1을 문자로 바꿔 출력하는 것이다. 이때 물론 0부터 1이 n개 나오는 경우까지만 더하면 된다.

그럼 순환문 안에 다음과 같은 처리 과정이 있어야 겠다.

1.숫자를 1더한다.
2.숫자의 1의 갯수를 센다.
3.1의 갯수와 k가 일치하면 출력한다.

순환문은 1의 갯수가 n개가 되면 빠져나온다.

1번 과정은 어떻게 구현할까?


순환문을 안에 다음과 같은 처리과정을 구현하면 된다.

1.배열의 i번 칸을 1 증가 시킨다.
2.배열의 i번 칸이 2가 되었는지 확인한다.
3.1.참이면 i번칸에 0을 대입하고 i--한다.
3.2거짓이면 순환문을 빠져나온다.

i>=0조건을 만족하지 못하면 빠져나와야 한다.

배열의 n-1번 칸부터 증가시켜 주려면 당연히 순환문 전에 i에 n-1을 대입해 줘야 한다.


#include <iostream>
#include <windows.h>
using namespace std;
int main(){
   
    int a[20]={0},n,k,i,c,ca=0;
   
    cin >>n >>k;
   
   
    while(true){
                i=n-1;
               
                while(i>=0){
                            a[i]++;
                            if(a[i]==2){
                                        a[i]=0;
                                        i--;
                            }else break;
                }
               
                c=0;
                for(i=0;i<n;i++){
                                 if(a[i]==1) c++;
                }
               
                if(c==k){
                         for(i=0;i<n;i++){
                                          if(a[i]==0) cout << "뒤";
                                          else cout << "앞";
                         }
                         cout<<endl;
                         ca++;
                }
               
                if(c==n){
                         break;
                }
    }
   
    cout << ca <<endl;
   
    system("PAUSE");
   
    return 0;
}
   
실행결과

8 5
뒤뒤뒤앞앞앞앞앞
뒤뒤앞뒤앞앞앞앞
뒤뒤앞앞뒤앞앞앞
뒤뒤앞앞앞뒤앞앞
뒤뒤앞앞앞앞뒤앞
뒤뒤앞앞앞앞앞뒤
뒤앞뒤뒤앞앞앞앞
뒤앞뒤앞뒤앞앞앞
뒤앞뒤앞앞뒤앞앞
뒤앞뒤앞앞앞뒤앞
뒤앞뒤앞앞앞앞뒤
뒤앞앞뒤뒤앞앞앞
뒤앞앞뒤앞뒤앞앞
뒤앞앞뒤앞앞뒤앞
뒤앞앞뒤앞앞앞뒤
뒤앞앞앞뒤뒤앞앞
뒤앞앞앞뒤앞뒤앞
뒤앞앞앞뒤앞앞뒤
뒤앞앞앞앞뒤뒤앞
뒤앞앞앞앞뒤앞뒤
뒤앞앞앞앞앞뒤뒤
앞뒤뒤뒤앞앞앞앞
앞뒤뒤앞뒤앞앞앞
앞뒤뒤앞앞뒤앞앞
앞뒤뒤앞앞앞뒤앞
앞뒤뒤앞앞앞앞뒤
앞뒤앞뒤뒤앞앞앞
앞뒤앞뒤앞뒤앞앞
앞뒤앞뒤앞앞뒤앞
앞뒤앞뒤앞앞앞뒤
앞뒤앞앞뒤뒤앞앞
앞뒤앞앞뒤앞뒤앞
앞뒤앞앞뒤앞앞뒤
앞뒤앞앞앞뒤뒤앞
앞뒤앞앞앞뒤앞뒤
앞뒤앞앞앞앞뒤뒤
앞앞뒤뒤뒤앞앞앞
앞앞뒤뒤앞뒤앞앞
앞앞뒤뒤앞앞뒤앞
앞앞뒤뒤앞앞앞뒤
앞앞뒤앞뒤뒤앞앞
앞앞뒤앞뒤앞뒤앞
앞앞뒤앞뒤앞앞뒤
앞앞뒤앞앞뒤뒤앞
앞앞뒤앞앞뒤앞뒤
앞앞뒤앞앞앞뒤뒤
앞앞앞뒤뒤뒤앞앞
앞앞앞뒤뒤앞뒤앞
앞앞앞뒤뒤앞앞뒤
앞앞앞뒤앞뒤뒤앞
앞앞앞뒤앞뒤앞뒤
앞앞앞뒤앞앞뒤뒤
앞앞앞앞뒤뒤뒤앞
앞앞앞앞뒤뒤앞뒤
앞앞앞앞뒤앞뒤뒤
앞앞앞앞앞뒤뒤뒤
56
Press any key to continue . . .