백준 : 15652번 N과 M(4) (c++)

백준 링크

https://www.acmicpc.net/problem/15652

15652번: N과 M (4)

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	512 MB	44391	34904	27989	78.723%

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1

예제 출력 1

1
2
3

예제 입력 2

4 2

예제 출력 2

1 1
1 2
1 3
1 4
2 2
2 3
2 4
3 3
3 4
4 4

코드 풀이

이전 문제에 이어서 비슷한 유형의 코테를 더 풀어보았다.

이번 문제는 예제를 보면 Array[i + 1] 값이 Array[i]값보다 같거나 커야한다는것을 알 수 있다.

그래서 int J = 1;을 초기값으로 선언하였고

K가 0이 아니라면 뒤에 오는 인덱스이기 때문에 J = Array[K - 1]을 해주고

반복문 선언부분에 i = J로 구성하였다.

또한 이번 문제는 백트래킹이 필요없는 부분이라 기존에 사용하던 방문 관련 배열은 제거하였다.

코드

#include <iostream>

using namespace std;

int Array[9];

int N, M;

void Func(int K)
{
    if (K == M)
    {
        for (int i = 0; i < K; ++i)
        {
            cout << Array[i] << ' ';
        }

        cout << '\n';

        return;
    }

    int J = 1;

    if (K != 0)
        J = Array[K - 1];

    for (int i = J; i <= N; ++i)
    {
        Array[K] = i;
        Func(K + 1);
    }
}

int main()
{
    cin >> N >> M;

    Func(0);

    return 0;
}

 

 

관련 문제

https://tin9-d-d-blog.tistory.com/216

백준 : 15649번 : N과 M(1) (c++)

https://tin9-d-d-blog.tistory.com/217

백준 : 15650번 N과 M(2) (c++)