[C++] 백준 15649번 : N과 M (2)

15650번: N과 M (2)

---

문제

---

풀이

순서와 관련된 문제이다.

 

방법 1.

만약 N = 5, N = 3일 경우

1 2 3

1 2 4

1 2 5

1 3 2 → 1 3 4 (1 3 2는 오름차순이 아니므로)

1 3 5

  ···

와 같이 진행된다.

 

순서대로 진행되고 결과 수열이 오름차순이어야 하므로

첫 번째 자리는 1부터 시작하고 두 번째 자리의 숫자는 무조건 첫 번째 자리 숫자보다 큰 수가 나와야 한다.

마지막 자리 또한 무조건 두 번째 자리 숫자보다 큰 수가 나와야 한다.

즉, 중복이 안된다.

 

 

방법 2.

(문제에 대해 조사를 하던 도중 알게 된 새로운 방법!)

결과 수열은 오름차순이므로 수열의 자리마다 어떤 수가 들어갈지 결정이 가능하다.

즉, 수열에 포함하는 경우와 수열에 미포함하는 경우를 전부 구하여 수열을 구할 수 있다.

 

위와 같은 방법을 사용하면 방법 1. 보다 더 빠른 시간 복잡도로 구현이 가능하다.

---

문제점

재귀 함수를 사용할 경우 직접 손으로 써보면서 확인을 해보는 습관을 가져야 할 것 같다...

---

코드

#include <iostream>
using namespace std;

int a[8];

// 방법 1.
/*
void go(int index, int start, int n, int m)
{
    if (index == m)
    {
        for (int i = 0; i < m; ++i)
        {
            cout << a[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= n; ++i)
    {
        a[index] = i;
        go(index + 1, i + 1, n ,m);
    }
}
*/

// 방법 2
void go(int index, int selected, int n, int m)
{
    if (selected == m)
    {
        for (int i = 0; i < m; ++i)
        {
            cout << a[i] << " ";
        }
        cout << "\n"; 
        return;
    }

    if (index > n)
    {
        return;
    }
    // 수열에 포함, 즉 index를 결과에 추가
    a[selected] = index;
    go(index + 1, selected + 1, n, m);
    // 수열에 미포함, 즉 index를 결과에 추가 안함
    a[selected] = 0;
    go(index + 1, selected, n, m);
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

	// 방법 1.
    //go(0, 1, n, m);
    
    // 방법 2.
    go(1, 0, n, m);

}

---

결과

방법 1. : 아래

방법 2. : 위

---

 

 

 

pyo7410/Study