본문 바로가기

N과M7

[BOJ] 15651. N과 M (3) https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M (3)은 N과 M (1)과 달리 같은 수를 여러 번 골라도 된다는 조건이 있기 때문에 visited[] 배열을 관리할 필요가 없다는 차이점이 있다. #include #include #include using namespace std; int N, M; int numbers[7]; vector series; void dfs(int cnt); void print(); int main.. 2019. 4. 16.
[BOJ] 15650. N과 M (2) https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해야 한다. www.acmicpc.net N과 M (2)가 N과 M (1)의 다른 점은 N과 M (2)는 조합이고, N과 M (1)은 순열이라는 점이다. N과 M (2)가 (1)과 달리 조합인 이유는 '고른 수열은 오름차순이어야 한다.' 라는 조건 때문이다. 1부터 4까지의 숫자로 2개의 수를 골라 수열을 만들었을 때, '고른 수열은 오름차순이어야 한다.' 라는 조건이 없다면? 순열로 {1, 2}, {1, 3}, {1, 4}, .. 2019. 4. 16.
[BOJ] 15649. N과 M (1) https://www.acmicpc.net/workbook/view/2052 문제집: N과 M (baekjoon) www.acmicpc.net 백준 사이트에 있는 N과 M 시리즈는 백트래킹, DFS의 기본을 다지기 좋다. 1부터 12까지 한번 쭉 풀어봤지만 다시 한번 풀어보며 포스팅을 해보려고 한다. 우선 N과 M 시리즈를 풀기 전에 순열과 조합에 대한 개념을 알아둬야 한다. 순열이란 순서가 상관이 있는 모임이다. 순열에 있어서 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}은 모두 다른 것으로 취급된다. 조합은 순서가 상관이 없는 모임이다. 조합에 있어서 {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {.. 2019. 4. 16.

티스토리툴바