[백준(BOJ)] 15657번 : N과 M (8) - C++[CPP]

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

15657번: N과 M (8)

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 백트래킹

 

---

 

⊙ 문제 접근 과정

 

문제의 세 번째 제한조건을 보자.

 

• 고른 수열은 비내림차순이어야 한다.

 

이 조건을 보고 나는 의아했다. 오름차순과 내림차순, 서로 반대말 아닌가?

그렇다는 건 비내림차순으로 나타내라면 그에 반대인 오름차순으로 나타내라는 건가?

 

그리고 예제 입출력을 봤다.

오름차순이다. 내 생각이 어느 정도 맞았다는 것을 입증했다.

 

그리고 난 또 궁금했다.

그렇다면 왜 오름차순이라 안 하고 말장난(?)을 하여 비내림차순으로 하라고 적었을까?

 

확실히 짚고 넘어가고 싶었다.

내림차순의 반대말은 오름차순이고 오름차순의 반댓말은 내림차순이 맞다.

 

그렇지만 비내림차순이 오름차순은 아니다.

비내림차순이 뜻하는 바는 "내림차순이 아니다"이다. 말 그대로 비내림차순

 

그러니 비내림차순은 오름차순이 될 수도 있지만 내림차순만 아니면 된다는 뜻이다.

 

코드는 이전 단계에서 살짝만 수정했다. 어려운 건 없다.

---

 

⊙ 문제 풀이

 

#include <iostream>
#include <algorithm>

using namespace std;
#define MAX 9

int N,M;
int first[MAX];
int arr[MAX];

void dfs(int num, int k) { //현재 위치
    if(k==M) { //목표인 M까지 도달했다면
        for(auto i =0;i<M;i++)
            cout << arr[i] << " "; //arr에 저장한 값 M개 만큼 출력
        cout << "\n";
    }else { //목표에 도달하지 않았다면
        for(auto i=num; i<N;i++) {
            arr[k]=first[i]; // 정렬한 N값을 arr에 저장
            dfs(i, k+1); //더 깊게 들어가자. (M까지)
        }
    }
}

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

    for(int i=0;i<N;i++)
        cin >> first[i];
    
    sort(first,first+N); //정렬

    dfs(0, 0);
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

15649번 : N과 M (1)

15650번 : N과 M (2)

15651번 : N과 M (3)

15652번 : N과 M (4)

15654번 : N과 M (5)

15654번 : N과 M (6)

15656번 : N과 M (7)

15657번 : N과 M (8)

15663번 : N과 M (9)

15664번 : N과 M (10)

15665번 : N과 M (11)

15666번 : N과 M (12)

 

 

좋아요는 로그인하지 않아도 누를 수 있습니다!