JArchive 프로그래밍 일기

문제

N과M(3) 백준 15651번

리뷰

오름차순 수열을 출력하되, *숫자 중복을 허용한다. *

코드

#include <iostream>
#include <algorithm> 
using namespace std;

/*  n과m (3)
중복 허용
1부터 n까지 자연수 중에서 m개를 고른 수열  
*/ 

int n, m;
int arr[10]; // 출력할 수열을 담는다.  

void go(int index){  // index 0부터 m-1 까지 어떤 수로 채울지 선택하는 함수  

    if(index == m){ // index m-1까지 모든 수를 골랐으니까 수열 출력 

        for(int i = 0; i < m; i++){ // 수열 출력
            printf("%d ", arr[i]);
        }
        cout << '\n';        
        return; 
    } 

    for(int i = 1; i <= n; i++){ // 1부터 n까지 수를 '중복 허용'하여 선택
        arr[index] = i;
        go(index+1); // 다음 자리 숫자를 고르러 재귀호출 
    }

}

int main(void){

       scanf("%d %d", &n, &m);

      go(0); // 0번째 자리에 어떤 수를 넣을지 선택한다.  

    return 0;
} 

문제

N과M(4) 백준 15652번

리뷰

비내림차순 수열을 출력하되, *숫자 중복을 허용한다. *

비내림차순은 '같은 숫자가 연속되거나 오름차순'이다. 예를 들어, 11223 같은 수열이 비내림차순이다.

중복 허용이니까 중복체크할 배열이 필요 없다.

코드 1

#include <iostream>
using namespace std;


/*   n과m (4)
중복 허용, 비내림차순  
1부터 n까지 자연수 중에서 m개를 고른 수열  
*/ 

int n, m;
int arr[10]; // 출력할 수열을 담는다.  

void go(int index, int start_num){  

    if(index == m){ // 수열 출력
        for(int i = 0; i < m; i++){
            printf("%d ", arr[i]);
        }
        cout << '\n';
        return; 
    } 

    for(int i = start_num; i <= n; i++){ // 선택 범위의 시작 숫자만 정해준다. 
        arr[index] = i; 
        go(index+1, i); // 반드시 i 보다 큰 수부터 다시 선택해야 하는게 아니다.(비내림차순)
    }

}

int main(void){

       scanf("%d %d", &n, &m);

      go(0, 1); // 0번째 자리에 어떤 수를 넣을지 선택한다.  start는 선택범위의 시작숫자. 

    return 0;
} 

코드 2

m 개로 이루어진 배열 arr를 채우는 '완전탐색' DFS로 풀이했다.

#include <iostream>
using namespace std;

/*  n과m (4)  DFS로 푼 코드 
중복 허용, 비내림차순  
1부터 n까지 자연수 중에서 m개를 고른 수열  
*/ 

int n, m;
int arr[10]; // 숫자 m개를 골라 저장할 수열  

void dfs(int start_num, int cnt){ // 비내림차순 이니까 start_num 활용.  cnt는 선택한 숫자 개수

    if(cnt == m){ // 0 ~ m-1 까지 총 m 개 선택 완료해서 수열을 출력.
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }

    for(int i = start_num; i <= n; i++){ // 비내림차순
        arr[cnt] = i;  // cnt자리에 i숫자를 넣는다. 선택한 것.
        dfs(i, cnt+1); 
        // 비내림차순이니까 i 부터 다시 선택할 수 있게 한다. 윗줄에서 선택했으니 cnt+1을 넘긴다. 
    }
} 


int main(void){

      scanf("%d %d", &n, &m);

      dfs(1, 0);  // 1부터 시작한다. 고른 개수.

    return 0;
}