1. N과 M (1)
https://www.acmicpc.net/problem/15649
구현
- N까지의 수에서 M개를 뽑는 경우의 수를 구하는 문제.
- 계층을 가지는 DFS로 구현하면 된다.
문제점
1. DFS를 구현하기 헷갈렸다.
#include <iostream>
using namespace std;
int N, M;
int arr[9]; // 답을 저장하는 배열
bool visited[9]; // DFS 방문확인 배열
void DFS(int n)
{
if(n==M) // M 개수를 채웠다면, 출력 후 종료
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else // M 개수를 채우지 못했다면, DFS를 타고 들어감.
{
for(int i=1;i<=N;i++)
{
if(!visited[i])
{
visited[i] = true;
arr[n] = i;
DFS(n+1);
visited[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
DFS(0);
return 0;
}2. N과 M (2)
https://www.acmicpc.net/problem/15650
구현
- 기존의 NM에 추가로 수의 조합이 중복이 되면 안된다.
- 마지막 원소의 값을 알려주도록 추가하면 된다.
- 마지막 값 이후의 값들만 추가하도록 하면,
중복을 방지할 수 있기 때문
문제점
1.DFS(0, 1)로 main에서 시작해야하는게 위화감이 들었었다.
#include <iostream>
using namespace std;
int N, M;
int arr[9]; // 답을 저장하는 배열
bool visited[9]; // DFS 방문확인 배열
void DFS(int n, int num) // 1 num을 추가함으로써
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=num;i<=N;i++) // 2 num 다음의 값들만 다루도록 함
{
if(!visited[i])
{
visited[i] = true;
arr[n] = i;
DFS(n+1, i);
visited[i] = false;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
DFS(0, 1); // 현재 개수는 0이고, 1이 들어가면 식이 시작이 됨.
return 0;
}3. N과 M (3)
https://www.acmicpc.net/problem/15651
구현
- 기존의 NM에 추가로 11 22 33 44 이런 중복도 가능하게 한다.
- visited를 다르게 구성하면 된다.
문제점
- 없
#include <iostream>
using namespace std;
int N, M;
int arr[8];
int visited[8]; // int형으로 구현하여 중복방문 가능
void DFS(int n)
{
if (n == M)
{
for (int i = 0; i < M; i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for (int i = 1; i <= N; i++)
{
if (visited[i] < M)
{
visited[i]++;
arr[n] = i;
DFS(n+1);
visited[i]--;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
DFS(0);
return 0;
}4. N과 M (4)
https://www.acmicpc.net/problem/15652
구현
- NM2, NM3의 추가조건을 동시에 만족하도록 해야한다.
- 기존 NM3의 식에 int num을 받도록 수정하면 된다.
문제점
- 없
DFS만 추가한다.
void DFS(int n, int num)
{
if (n == M)
{
for (int i = 0; i < M; i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for (int i = num; i <= N; i++)
{
if (visited[i] < M)
{
visited[i]++;
arr[n] = i;
DFS(n+1, i);
visited[i]--;
}
}
}
}5. N과 M (5)
https://www.acmicpc.net/problem/15654
구현
- 기존의 NM에 추가로 원소 배열을 받는다.
- 해당 원소 배열의 값으로 조합해야만 한다.
- vector를 생성하여 원소를 받고, 오름차순으로 정렬하였다.
- 그리고 아래의 코드처럼 실행.
- 단순히
arr[n] = v[i]이 부분만 바뀐 것 말고 NM과 똑같다.
문제점
1. 아래 주석 표시된 부분이 헷갈렸다.
void DFS(int n)
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=0;i<N;i++)
{
if (!visited[i])
{
visited[i] = true;
arr[n] = v[i]; // 문제된 부분
DFS(n+1);
visited[i] = false;
}
}
}
}6. N과 M (6)
https://www.acmicpc.net/problem/15655
구현
- NM5에 추가로 중복된 수열이 있으면 안된다.
- 여태 했던 것처럼 int num을 추가한다.
- 그리고 main에서 DFS의 시작을 아래와 같이 해야했다.
DFS(0, 0); // 기존의 NM과 다르게 0부터 시작해야 함 (Vector기 때문)문제점
- 없
7. N과 M (7)
https://www.acmicpc.net/problem/15656
구현
- NM5에 추가로 같은 수를 여러번 골라도 된다.
- 여태 했던 것처럼 visited를 int형으로 바꾼다.
void DFS(int n)
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=0;i<N;i++)
{
if (visited[i] < M)
{
visited[i]++;
arr[n] = v[i];
DFS(n+1);
visited[i]--;
}
}
}
}문제점
- 그냥 하면 된다.
8. N과 M (8)
https://www.acmicpc.net/problem/15657
구현
- NM6, NM7의 조건을 합치면 된다.
- 중복 수열X, 수 여러번O
문제점
- 없
void DFS(int n, int num)
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=num;i<N;i++)
{
if (visited[i]<M)
{
visited[i]++;
arr[n] = v[i];
DFS(n+1, i);
visited[i]--;
}
}
}
}9. N과 M (9)
https://www.acmicpc.net/problem/15663
구현
- 기존의 NM에 추가로 원소 배열을 받는다.
이때, 원소 배열에 중복된 수가 존재한다.- 중복된 수는 해당 개수만큼 중복해서 사용할 수 있다.
- num_count라는 수의 개수를 셀 배열을 하나 만들었다.
문제점
- 없
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int arr[9];
int visited[9] = {0, }; // visited도 int로 선언, 중복이 있을 수 있기 때문
int num_count[10001] = {0,}; // 숫자가 몇 개 입력으로 주어졌는지 확인
vector<int> v;
void DFS(int n)
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=0;i<N;i++)
{
if(visited[i] < num_count[v[i]]) // 핵심코드
{
visited[i]++;
arr[n] = v[i];
DFS(n+1);
visited[i]--;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int num;
cin >> num;
if(!num_count[num])
{
v.push_back(num);
}
num_count[num]++;
}
sort(v.begin(), v.end());
DFS(0);
return 0;
}10. N과 M (10)
https://www.acmicpc.net/problem/15664
구현
- NM9에 중복수열X = int num 추가
11. N과 M (11)
https://www.acmicpc.net/problem/15665
구현
- NM9에 같은 수 여러번 = visited < M 해줌
- 아래 for문의 범위에 주의.
vector는 중복된 값을 받으면 push하지 않는데,
N번의 입력에 중복된 값이 존재하므로, N보다 무조건 이하이다.
따라서 그냥 vector의 size까지만 하면 정상동작.
for(int i=0;i<v.size();i++)
{
if(visited[i] < M) // 핵심코드
{
visited[i]++;
arr[n] = v[i];
DFS(n+1);
visited[i]--;
}
}12. N과 M (12)
https://www.acmicpc.net/problem/15666
구현
- NM10, NM11 합침
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int N, M;
int arr[9];
int visited[9] = {0, }; // visited도 int로 선언, 중복이 있을 수 있기 때문
int num_count[10001] = {0,}; // 숫자가 몇 개 입력으로 주어졌는지 확인
vector<int> v;
void DFS(int n, int num)
{
if(n==M)
{
for(int i=0;i<M;i++)
{
cout << arr[i] << " ";
}
cout << "\n";
}
else
{
for(int i=num;i<v.size();i++)
{
if(visited[i] < M) // 핵심코드
{
visited[i]++;
arr[n] = v[i];
DFS(n+1, i);
visited[i]--;
}
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for(int i=0;i<N;i++)
{
int num;
cin >> num;
if(!num_count[num])
{
v.push_back(num);
}
num_count[num]++;
}
sort(v.begin(), v.end());
DFS(0,0);
return 0;
}N과 M문제
N과 M 문제를 풀며, 기출변형이 된 부분은 아래와 같다.
- 1. NM 원본
- 개수만 매개변수로 가지는 DFS 돌리면 된다.
- 2. NM 순서만 다른 중복되는 수열 안됨
- int num까지 추가 매개변수로 가지는 DFS 돌리면 된다.
- 3. NM 같은 수를 여러번 골라도 된다
- visited를 bool에서 int로 수정하고, M을 넘지 않게 검사.
위의 내용들이 같이 나오는 경우, 같이 구현하면 됨.
기본적으로 큰 틀을 벗어나지 않았다.
Time Waits for No One