[BOJ] N과 M

마코레·2022년 6월 25일
0

코테공부

목록 보기
11/19

문제설명


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

1부터 N까지 자연수 중에서 중복없이 M개를 고른 수열

풀이


#include <iostream>
#define MAX 9

using namespace std;

int n,m;
int arr[MAX] = {0,};
bool visited[MAX] = {0,};

void dfs(int cnt)
{
    if(cnt == m)
    {
        for(int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for(int i = 1; i <= n; i++)
    {
        if(!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt+1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}
  • 백트래킹 문제
  • 재귀함수로 백트래킹 구현했음
    • for문으로 i=1~n까지 돌면서 그안에서 재귀함수를 호출하는 방식임
    • 그래서 번호순으로 차곡차곡 출력함!
    • 1234, 1243 이런식으로
    • 백트랙킹 끝났으면 visited를 false로 바꿔줌
profile
새싹 백엔드 개발자

0개의 댓글

관련 채용 정보

Powered by GraphCDN, the GraphQL CDN