띠그랭

삼성 코딩 테스트 기출 - 스타트와 링크 - 14889번

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

14 : 14 시작 —> 15:10 종료

일단 팀을 나누는데 순열(next_permutation) 한번… 여기까진 복잡하진 않았는데,

한 팀안에서 2명씩 또 골라야 돼서 순열(next_permutation) 한번.. 여기서 좀 복잡해졌다.

하지만 천천히 푸니깐 해결되었다. 좀 편안한 마음으로 코드를 짜야할거 같다. 소스도 좀 더럽게 나오기도 하고..

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최소값을 출력한다.

예제 입력 1

 
xxxxxxxxxx
4
0 1 2 3
4 0 5 6
7 1 0 2
3 4 5 0

예제 출력 1

 
xxxxxxxxxx
0

예제 입력 2

 
xxxxxxxxxx
6
0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0

예제 출력 2

 
xxxxxxxxxx
2

예제 입력 3

 
xxxxxxxxxx
8
0 5 4 5 4 5 4 5
4 0 5 1 2 3 4 5
9 8 0 1 2 3 1 2
9 9 9 0 9 9 9 9
1 1 1 1 0 1 1 1
8 7 6 5 4 0 3 2
9 1 9 1 9 1 0 9
6 5 4 3 2 1 9 0

예제 출력 3

 
1

소스 코드

 
x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int N;
vector<vector<int>> v;
vector<int> start;  // start 팀
vector<int> link;   // link 팀
vector<int> d;  // 두 팀으로 나눌 때 쓸 vector
int min_result = 987654321;
​
void input()
{
    cin >> N;
    v.resize(N+1, vector<int>(N+1));
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cin >> v[i][j];
    }
}
​
void team_divide()
{
    start.clear();      // 다음 start팀을 위한 초기화
    link.clear();       // 다음 link팀을 위한 초기화
    for (int i = 0; i < d.size(); i++)
    {
        if (d[i] == 0)
            start.push_back(i);
        else if (d[i] == 1)
            link.push_back(i);
    }
}
​
int calc(vector<int> &team)     // 팀에서 2명을 골라 능력치 합 구하기
{
    vector<int> tmp;
    for (int i = 0; i < start.size() - 2; i++)
        tmp.push_back(0);
    for (int i = 0; i < 2; i++)
        tmp.push_back(1);
​
    int res = 0;
    int cnt;
    int n[2];
    do {
        cnt = 0;
        
        for (int i = 0; i < tmp.size(); i++)
        {
            if (tmp[i] == 1)
                n[cnt++] = team[i] + 1;
        }
        res += v[n[0]][n[1]] + v[n[1]][n[0]];
    } while (next_permutation(tmp.begin(), tmp.end()));
​
​
    return res;
}
​
int main()
{
    input();
​
    for (int i = 0; i < N / 2; i++)
        d.push_back(0);
    for (int i = 0; i < N / 2; i++)
        d.push_back(1);
​
    do {
        team_divide();
        int num1 = calc(start);
        int num2 = calc(link);
​
        min_result = min(min_result, abs(num1 - num2));
​
    } while (next_permutation(d.begin(), d.end()));
​
    cout << min_result << '\n';
​
    return 0;
}

삼성 코딩 테스트 기출 - 연산자 끼워넣기 14888번 (완전탐색 - 순열)

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

13시 50분 시작 —> 14시 05분 종료

완전탐색 - 순열 편에서 공부했던 바로 그 스킬을 쓰면 단번에 풀수 있는 완전탐색문제이다.

일단 조건이 좀 쉬운편인데 숫자는 가만히 있고, 연산자들만 나올 수 있는 모든 조합을 만들면 되기 때문에,

next_permutation을 가지고 슈르륵 쥬르륵 돌려서 한번 돌릴때마다 결과값을 구해 , if문을 통해 비교하면 끝 , calc() 함수에서 if문 4개는 배열을 이용하면 코드를 더 이쁘게 잘 수 있을거 같긴한데, 일단 무조건 빨리 푸는게 짱짱맨이니까, 나중에 시간나면 고쳐야딩

문제

N개의 수로 이루어진 수열 A1, A2, ..., AN이 주어진다. 또, 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자가 주어진다. 연산자는 덧셈(+), 뺄셈(-), 곱셈(×), 나눗셈(÷)로만 이루어져 있다.

우리는 수와 수 사이에 연산자를 하나씩 넣어서, 수식을 하나 만들 수 있다. 이 때, 주어진 수의 순서를 바꾸면 안된다.

예를 들어, 6개의 수로 이루어진 수열이 1, 2, 3, 4, 5, 6이고, 주어진 연산자가 덧셈(+) 2개, 뺄셈(-) 1개, 곱셈(×) 1개, 나눗셈(÷) 1개인 경우에는 총 60가지의 식을 만들 수 있다. 예를 들어, 아래와 같은 식을 만들 수 있다.

• 1+2+3-4×5÷6
• 1÷2+3+4-5×6
• 1+2÷3×4-5+6
• 1÷2×3-4+5+6

식의 계산은 연산자 우선순위를 무시하고 앞에서부터 진행해야 한다. 또, 나눗셈은 정수 나눗셈으로 몫만 취한다. 음수를 양수로 나눌 때는 C의 기준을 따른다. 즉 양수로 바꾼 뒤 몫을 취하고, 그 몫을 음수로 바꾼 것과 같다. 이에 따라서, 위의 식 4개의 결과를 계산해보면 아래와 같다.

• 1+2+3-4×5÷6 = 1
• 1÷2+3+4-5×6 = 12
• 1+2÷3×4-5+6 = 5
• 1÷2×3-4+5+6 = 7

N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱셈(×)의 개수, 나눗셈(÷)의 개수이다.

출력

첫째 줄에 만들 수 있는 식의 결과의 최대값을, 둘째 줄에는 최소값을 출력한다. 최대값과 최소값은 항상 -10억보다 크거나 같고, 10억보다 작거나 같은 결과가 나오는 입력만 주어진다. 또한, 앞에서 부터 계산했을 때, 중간에 계산되는 식의 결과도 항상 -10억보다 크거나 같고, 10억보다 작거나 같다.

예제 입력 1

 
xxxxxxxxxx
2
5 6
0 0 1 0

예제 출력 1

 
xxxxxxxxxx
30
30

예제 입력 2

 
xxxxxxxxxx
3
3 4 5
1 0 1 0

예제 출력 2

 
xxxxxxxxxx
35
17

예제 입력 3

 
xxxxxxxxxx
6
1 2 3 4 5 6
2 1 1 1

예제 출력 3

 
54
-24

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int N;  // 수의 갯수
vector<int> n;      // 숫자를 넣을 vector
vector<char> v;     // 연산자 넣을 vector
int res_max = -9876543210;
int res_min = 9876543210;
​
void input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        int tmp;
        cin >> tmp;
        n.push_back(tmp);
    }
    int plus, minus, mul, div;
    cin >> plus >> minus >> mul >> div;
    for (int i = 0; i < plus;i++)
        v.push_back('+');
    for (int i = 0; i < minus; i++)
        v.push_back('-');
    for (int i = 0; i < mul; i++)
        v.push_back('*');
    for (int i = 0; i < div; i++)
        v.push_back('/');
​
}
​
void calc()
{
    int res = n[0];
    for (int i = 1; i <= N - 1; i++)
    {
        int tmp_n = n[i];
        char tmp_v = v[i-1];
        if (tmp_v == '+')
            res = res + tmp_n;
        else if (tmp_v == '-')
            res = res - tmp_n;
        else if (tmp_v == '*')
            res = res * tmp_n;
        else if (tmp_v == '/')
            res = res / tmp_n;
    }
    if (res_max < res)
        res_max = res;
    if (res_min > res)
        res_min = res;
​
}
​
int main()
{
    input();
​
    sort(v.begin(), v.end());
​
    do {
        calc();
    } while (next_permutation(v.begin(), v.end()));
    
    cout << res_max << '\n';
    cout << res_min << '\n';
​
    return 0;
}
​

삼성 코딩 테스트 기출 - 퇴사 14501번 (DFS)

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

16시 44분 시작 —> 17시 53분 종료

아 배열 선언을 16을 해야하는데 15을 하는 바람에 진짜 엄한 곳에서 시간을 20분동안 잡아먹었다.

정신차리자 띠그랭..

이문제는 기본적인 재귀호출 완전탐색 문제이다.

문제

상담원으로 일하고 있는 백준이는 퇴사를 하려고 한다.

오늘부터 N+1일째 되는날 퇴사를 하기 위해서, 남은 N일 동안 최대한 많은 상담을 하려고 한다.

백준이는 비서에게 최대한 많은 상담을 잡으라고 부탁을 했고, 비서는 하루에 하나씩 서로 다른 사람의 상담을 잡아놓았다.

각각의 상담은 상담을 완료하는데 걸리는 기간 Ti와 상담을 했을 때 받을 수 있는 금액 Pi로 이루어져 있다.

N = 7인 경우에 다음과 같은 상담 일정표를 보자.

1일에 잡혀있는 상담은 총 3일이 걸리며, 상담했을 때 받을 수 있는 금액은 10이다. 5일에 잡혀있는 상담은 총 2일이 걸리며, 받을 수 있는 금액은 15이다.

상담을 하는데 필요한 기간은 1일보다 클 수 있기 때문에, 모든 상담을 할 수는 없다. 예를 들어서 1일에 상담을 하게 되면, 2일, 3일에 있는 상담은 할 수 없게 된다. 2일에 있는 상담을 하게 되면, 3, 4, 5, 6일에 잡혀있는 상담은 할 수 없다.

또한, N+1일 째에는 회사에 없기 때문에, 6, 7일에 있는 상담을 할 수 없다.

퇴사 전에 할 수 있는 상담의 최대 이익은 1일, 4일, 5일에 있는 상담을 하는 것이며, 이 때의 이익은 10+20+15=45이다.

상담을 적절히 했을 때, 백준이가 얻을 수 있는 최대 수익을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (1 ≤ N ≤ 15)이 주어진다.

둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti≤ 5, 1 ≤ Pi ≤ 1,000)

출력

첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다.

예제 입력 1

 
xxxxxxxxxx
7
3 10
5 20
1 10
1 20
2 15
4 40
2 200

예제 출력 1

 
xxxxxxxxxx
45

예제 입력 2

 
xxxxxxxxxx
10
1 1
1 2
1 3
1 4
1 5
1 6
1 7
1 8
1 9
1 10

예제 출력 2

 
xxxxxxxxxx
55

예제 입력 3

 
xxxxxxxxxx
10
5 10
5 9
5 8
5 7
5 6
5 10
5 9
5 8
5 7
5 6

예제 출력 3

 
xxxxxxxxxx
20

예제 입력 4

 
xxxxxxxxxx
10
5 50
4 40
3 30
2 20
1 10
1 10
2 20
3 30
4 40
5 50

예제 출력 4

 
90

소스 코드

 
x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int N;  // 총 기간
int arr[16][2];     // [][0] : 완료 기간 , [][1] : 받을 금액
int max_profit;
​
void input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> arr[i][0] >> arr[i][1];
    }
}
​
void DFS(int n, int sum)
{
    if (n == N + 1)
    {
        if (max_profit < sum)
            sum = max_profit;
        return;
    }
    
    if (n + arr[n][0] <= N + 1) DFS(n + arr[n][0], sum + arr[n][1]);
    DFS(n + 1, sum);
}
​
int main()
{
    input();
​
    DFS(1,0);
​
    cout << max_profit << '\n';
​
    return 0;
}

삼성 코딩 테스트 기출 - 로봇청소기 14503번

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

15시 38분 시작 —> 16시 25분 종료

while문 안에서 continue를 통해 무한 루프 도는 것처럼 코드를 짯으며, 위에 쭈루룩 조건이 맞지 않는다면 로봇 청소기는 움직일수 없다는 것이므로 break를 통해 빠져나오는 단순 구현 문제이다.

하지만 나는 이런 문제가 좀 어려운거 같다. 단순 구현이긴 하지만 막상 머리에 있는 알고리즘을 소스 코드로 나타내는 건 너무 어려운거 같드아.

아 그리고 마지막 후진하기에서 4개의 if문은 for문을 통해라던가 , 아니면 다른 방식을 통해 코드를 줄일 수 있을 거 같긴하지만, 최대한 빨리 풀어보기 위해 좀 더럽게 짠 감이 있다.

문제

로봇 청소기가 주어졌을 때, 청소하는 영역의 개수를 구하는 프로그램을 작성하시오.

로봇 청소기가 있는 장소는 N×M 크기의 직사각형으로 나타낼 수 있으며, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 벽 또는 빈 칸이다. 청소기는 바라보는 방향이 있으며, 이 방향은 동, 서, 남, 북중 하나이다. 지도의 각 칸은 (r, c)로 나타낼 수 있고, r은 북쪽으로부터 떨어진 칸의 개수, c는 서쪽으로 부터 떨어진 칸의 개수이다.

로봇 청소기는 다음과 같이 작동한다.

1. 현재 위치를 청소한다.

2. 현재 위치에서 현재 방향을 기준으로 왼쪽방향부터 차례대로 탐색을 진행한다.

   1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진하고 1번부터 진행한다.
   2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전하고 2번으로 돌아간다.
   3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진을 하고 2번으로 돌아간다.
   4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춘다.

로봇 청소기는 이미 청소되어있는 칸을 또 청소하지 않으며, 벽을 통과할 수 없다.

입력

첫째 줄에 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 50)

둘째 줄에 로봇 청소기가 있는 칸의 좌표 (r, c)와 바라보는 방향 d가 주어진다. d가 0인 경우에는 북쪽을, 1인 경우에는 동쪽을, 2인 경우에는 남쪽을, 3인 경우에는 서쪽을 바라보고 있는 것이다.

셋째 줄부터 N개의 줄에 장소의 상태가 북쪽부터 남쪽 순서대로, 각 줄은 서쪽부터 동쪽 순서대로 주어진다. 빈 칸은 0, 벽은 1로 주어진다. 장소의 모든 외곽은 벽이다.

로봇 청소기가 있는 칸의 상태는 항상 빈 칸이다.

출력

로봇 청소기가 청소하는 칸의 개수를 출력한다.

예제 입력 1

 
xxxxxxxxxx
3 3
1 1 0
1 1 1
1 0 1
1 1 1

예제 출력 1

 
xxxxxxxxxx
1

예제 입력 2

 
xxxxxxxxxx
11 10
7 4 0
1 1 1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 1 1 1 1 0 1
1 0 0 1 1 0 0 0 0 1
1 0 1 1 0 0 0 0 0 1
1 0 0 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 1 1 0 1
1 0 0 0 0 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1

예제 출력 2

 
57

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<queue>
using namespace std;
​
int N, M;   // N : 세로 , M : 가로
int r, c, d;    // r : 초기 로봇 위치 세로 , c : 초기 로봇 위치 가로 , d : 초기 로봇 방향
int map[51][51];
int result;
int dir[4] = { 0,3,2,1 };   // 북 : 0 , 서 : 3 , 남 : 2 , 동 : 1
​
int dir_y[4] = {0, -1, 0, 1};   // [0]에는 북쪽방향일 때 왼쪽 , [1]에는 동쪽방향일 때 왼쪽
int dir_x[4] = { -1, 0, 1, 0};
​
void input()
{
    cin >> N >> M;
    cin >> r >> c >> d;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < M; j++)
        {
            cin >> map[i][j];
        }
    }
}
​
​
int main()
{
    input();
​
    while (1)
    {
        int sw = 0;
        // 1. 현재 위치 청소
        if (!map[r][c])
        {
            map[r][c] = 2;
            result++;
        }
​
        // 2-1 ~ 2-2. 현재 위치에서 왼쪽 방향부터 차례대로 탐색
        for (int i = 0; i < 4; i++)
        {
            int next_y = r + dir_y[d];
            int next_x = c + dir_x[d];
            if (next_y < 0 || next_x < 0 || next_y >= N || next_x >= M) continue;
            d--;
            if (d < 0) d = 3;
​
            if (!map[next_y][next_x]) // 2-1이 충족
            {
                r = next_y;
                c = next_x;
                sw = 1;
            }
            if (sw == 1) break;
        }
​
        if (sw == 1) continue;
​
        // 2-3 후진하기
        if (d == 0)
        {
            if (map[r + 1][c] != 1) // 뒤가 벽이 아닐 때
            {
                r = r + 1;
                continue;
            }
        }
        else if (d == 1)
        {
            if (map[r][c - 1] != 1)
            {
                c = c - 1;
                continue;
            }
        }
        else if (d == 2)
        {
            if (map[r - 1][c] != 1)
            {
                r = r - 1;
                continue;
            }
        }
        else if (d == 3)
        {
            if (map[r][c + 1] != 1)
            {
                c = c + 1;
                continue;
            }
        }
        
        break;
    }
​
    cout << result << '\n';
​
    return 0;
}

삼성 코딩 테스트 기출 - 연구소 14502번 (DFS , BFS)

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

13시 47분 시작 —> 14시 53분 종료

중간에 딴 짓을 한 시간까지 포함하면 이 문제를 푸는데 1시간 정도 걸렸다.

정답 비율이 50%가 넘어 금방 풀줄 알았는데 막상 풀어보니 DFS와 BFS를 동시에 쓰니 좀 어려웠다.

벽을 세우는 재귀호출 - DFS 와 바이러스를 퍼트리는 Queue를 이용한 BFS를 이용하여 문제를 풀었다.

코드를 짜는 건 40분 정도 걸린 거 같은데, DFS에서 중간에 i, j 로 주어야 할 것을 row, col 로 주어 이걸 찾는데 오래 걸렸다.

문제

인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다.

연구소는 크기가 N×M인 직사각형으로 나타낼 수 있으며, 직사각형은 1×1 크기의 정사각형으로 나누어져 있다. 연구소는 빈 칸, 벽으로 이루어져 있으며, 벽은 칸 하나를 가득 차지한다.

일부 칸은 바이러스가 존재하며, 이 바이러스는 인접한 빈 칸으로 모두 퍼져나갈 수 있다. 새로 세울 수 있는 벽의 개수는 3개이며, 꼭 3개를 세워야 한다.

예를 들어, 아래와 같이 연구소가 생긴 경우를 살펴보자.

 
xxxxxxxxxx
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

이 때, 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 곳이다. 아무런 벽을 세우지 않는다면, 바이러스는 모든 빈 칸으로 퍼져나갈 수 있다.

2행 1열, 1행 2열, 4행 6열에 벽을 세운다면 지도의 모양은 아래와 같아지게 된다.

 
xxxxxxxxxx
2 1 0 0 1 1 0
1 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 1 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

바이러스가 퍼진 뒤의 모습은 아래와 같아진다.

 
xxxxxxxxxx
2 1 0 0 1 1 2
1 0 1 0 1 2 2
0 1 1 0 1 2 2
0 1 0 0 0 1 2
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

벽을 3개 세운 뒤, 바이러스가 퍼질 수 없는 곳을 안전 영역이라고 한다. 위의 지도에서 안전 영역의 크기는 27이다.

연구소의 지도가 주어졌을 때 얻을 수 있는 안전 영역 크기의 최대값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 지도의 세로 크기 N과 가로 크기 M이 주어진다. (3 ≤ N, M ≤ 8)

둘째 줄부터 N개의 줄에 지도의 모양이 주어진다. 0은 빈 칸, 1은 벽, 2는 바이러스가 있는 위치이다. 2의 개수는 2보다 크거나 같고, 10보다 작거나 같은 자연수이다.

빈 칸의 개수는 3개 이상이다.

출력

첫째 줄에 얻을 수 있는 안전 영역의 최대 크기를 출력한다.

예제 입력 1

 
xxxxxxxxxx
7 7
2 0 0 0 1 1 0
0 0 1 0 1 2 0
0 1 1 0 1 0 0
0 1 0 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 1 0 0 0 0 0

예제 출력 1

 
xxxxxxxxxx
27

예제 입력 2

 
xxxxxxxxxx
4 6
0 0 0 0 0 0
1 0 0 0 0 2
1 1 1 0 0 2
0 0 0 0 0 2

예제 출력 2

 
xxxxxxxxxx
9

예제 입력 3

 
xxxxxxxxxx
8 8
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
2 0 0 0 0 0 0 2
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

예제 출력 3

 
3

소스 코드

 
x
#include<iostream>
#include<queue>
​
using namespace std;
​
int N, M;   // N:세로, M:가로
int ori_map[9][9];  // map 원본
int chk_map[9][9];  // 바이러스를 퍼트릴때 쓸 check 배열
int result;     // 안전 가옥의 수
​
int dir_y[4] = {-1,0,1,0}; // 12시 방향부터
int dir_x[4] = {0,1,0,-1};
​
void input()
{
    cin >> N >> M;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= M; j++)
            cin >> ori_map[i][j];
    }
}
​
void BFS(int row,int col)
{
    queue<pair<int, int>> q;
    q.push({ col,row });
​
    while (1)
    {
        if (q.empty()) break;
        int here_col = q.front().first; // 현재 세로 위치
        int here_row = q.front().second; // 현재 가로 위치
        q.pop();
​
        for (int i = 0; i < 4; i++) // 4방향 검사
        {
            int y = here_col + dir_y[i];
            int x = here_row + dir_x[i];
            if (x < 1 || y < 1 || x > M || y > N) continue;
​
            if (ori_map[y][x] == 0 && chk_map[y][x] == 0)
            {
                q.push({y,x});
                chk_map[y][x] = 1;
            }
        }
    }
}
​
void check()
{
    int res = 0;
    for (int i = 1; i <= N; i++)  // check 배열 초기화
    {
        for (int j = 1; j <= M; j++)
            chk_map[i][j] = 0;
    }
​
    for (int i = 1; i <= N; i++)    // 바이러스 퍼트리기
    {
        for (int j = 1; j <= M; j++)
        {
            if (ori_map[i][j] == 2)
                BFS(j, i);
        }
    }
​
    for (int i = 1; i <= N; i++)    // 안전 가옥의 수 검사
    {
        for (int j = 1; j <= M; j++)
        {
            if (ori_map[i][j] == 0 && chk_map[i][j] == 0)
                res++;
        }
    }
    if (result < res)
        result = res;
}
​
void DFS(int n,int row,int col)
{
    if (n >= 3)
    {
        check();
        return;
    }
    int j = row;
    for (int i = col; i <= N; i++)
    {
        for (j; j <= M; j++)
        {
            if (ori_map[i][j] == 2 || ori_map[i][j] == 1) continue;
            {
                ori_map[i][j] = 1;
                if (j == M) DFS(n + 1, 1, i+1);
                else DFS(n + 1, j + 1, i);
                ori_map[i][j] = 0;
            }
        }
        j = 1;
    }
}
​
​
int main()
{
    input();    // 데이터 입력
​
    DFS(0,1,1); // 벽 세우기
​
    cout << result << '\n';
​
    return 0;
}

완전탐색 - BFS(큐를 이용하여 풀기 , 숨바꼭질 - 1697번 , 소수 경로 - 1963번 , DSLR - 9019번)

BFS를 이용하여 문제를 푼다는 것은 그래프에서 최단,최소의 경로를 구하는 문제

이 때 조건은 A -> B 로 가는 간선의 가중치가 모두 동일하거나, 1이 여야 한다.

문제를 풀어서 BFS를 느껴보자.

1) 숨바꼭질 - 1697번

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

문제

수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다.

수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다.

출력

수빈이가 동생을 찾는 가장 빠른 시간을 출력한다.

예제 입력

 
xxxxxxxxxx
5 17

예제 출력

 
4

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
​
using namespace std;
​
int BFS(int start, int end)
{
    queue<pair<int,int>> q;
    q.push({start, 0});
    int check[100001] = { 0 };
    check[start] = 1;
    while (1)
    {
        if (q.empty() || q.front().first == end) {
            return q.front().second;
            break;
        }
        int pos = q.front().first;
        int seq = q.front().second;
        q.pop();
​
        if (pos - 1 >= 0 && !check[pos - 1])
        {
            q.push({ pos - 1 , seq + 1 });
            check[pos - 1] = 1;
        }
​
        if (pos + 1 <= 100000 && !check[pos + 1])
        {
            q.push({ pos + 1 , seq + 1 });
            check[pos + 1] = 1;
        }
​
        if (pos * 2 <= 100000 && !check[pos * 2])
        {
            q.push({ pos * 2 , seq + 1 });
            check[pos * 2] = 1;
        }
    }
}
int main()
{
    int s, e;
    cin >> s >> e;
​
    int res = BFS(s, e);
​
    cout << res << '\n';
    return 0;
}
​

2) 소수 경로 - 1963번

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

문제

소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데:

• “이제 슬슬 비번 바꿀 때도 됐잖아”
• “응 지금은 1033으로 해놨는데... 다음 소수를 무엇으로 할지 고민중이야"
• “그럼 8179로 해”
• “흠... 생각 좀 해볼게. 이 게임은 좀 이상해서 비밀번호를 한 번에 한 자리 밖에 못 바꾼단 말이야. 예를 들어 내가 첫 자리만 바꾸면 8033이 되니까 소수가 아니잖아. 여러 단계를 거쳐야 만들 수 있을 것 같은데... 예를 들면... 1033 1733 3733 3739 3779 8779 8179처럼 말이야.”
• “흠...역시 소수에 미쳤군. 그럼 아예 프로그램을 짜지 그래. 네 자리 소수 두 개를 입력받아서 바꾸는데 몇 단계나 필요한지 계산하게 말야.”
• “귀찮아”

그렇다. 그래서 여러분이 이 문제를 풀게 되었다. 입력은 항상 네 자리 소수만(1000 이상) 주어진다고 가정하자. 주어진 두 소수 A에서 B로 바꾸는 과정에서도 항상 네 자리 소수임을 유지해야 하고, ‘네 자리 수’라 하였기 때문에 0039 와 같은 1000 미만의 비밀번호는 허용되지 않는다.

입력

첫 줄에 test case의 수 T가 주어진다. 다음 T줄에 걸쳐 각 줄에 1쌍씩 네 자리 소수가 주어진다.

출력

각 test case에 대해 두 소수 사이의 변환에 필요한 최소 회수를 출력한다. 불가능한 경우 Impossible을 출력한다.

예제 입력

 
xxxxxxxxxx
3
1033 8179
1373 8017
1033 1033

예제 출력

 
xxxxxxxxxx
6
7
0

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<queue>
#include<algorithm>
#include<string>
using namespace std;
​
int sosu[10000];
​
int change(int n, int i, int j)
{
    string num;
    num = to_string(n);
    num[i] = j + '0';
    return stoi(num);
}
​
int BFS(int start, int end)
{
    queue<pair<int, int>>q;
    q.push({ start , 0 });
    int chk[10000] = { 0 };
    while (1)
    {
        if (q.empty() || q.front().first == end)
            return q.front().second;
        int pos = q.front().first;
        int seq = q.front().second;
        q.pop();
​
        for (int i = 0; i < 4; i++)
        {
            for (int j = 0; j < 10; j++)
            {
                int tmp = change(pos, i, j);
                if (sosu[tmp] && !chk[tmp])
                {
                    q.push({tmp, seq + 1});
                    chk[tmp] = 1;
                }
            }
        }
    }
}
​
int main()
{
    int t;
    int s, e;
    cin >> t;
    for (int i = 2; i <= 9999; i++)
        sosu[i] = i;
​
    for (int i = 2; i <= 9999; i++)
    {
        if (!sosu[i]) continue;
        for (int j = i * 2; j <= 9999; j += i)
            sosu[j] = 0;
    }
​
    for (int i = 2; i <= 999; i++)
        sosu[i] = 0;
​
    for (int i = 0; i < t; i++)
    {
        cin >> s >> e;
        cout << BFS(s, e) << '\n';
    }
    return 0;
}

3) DSLR - 9019번

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

문제

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412 1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

입력

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

출력

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

예제 입력

 
xxxxxxxxxx
3
1234 3412
1000 1
1 16

예제 출력

 
xxxxxxxxxx
LL
L
DDDD

소스 코드

 
xxxxxxxxxx
#include <iostream>
#include <queue>
#include<string>
​
using namespace std;
​
// 9019
int main() {
    int n;
    cin >> n;
    while (n-- > 0) {
        int start, end;
        cin >> start >> end;
        bool check[20000] = {false};
        string dist[10000];
        check[start] = true;
        queue<int> q;
        q.push(start);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            int next = (x * 2) % 10000;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'D';
                check[next] = true;
            }
            next = x > 0 ? x - 1 : 9999;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'S';
                check[next] = true;
            }
            int top = x / 1000;
            next = (x % 1000) * 10 + top;
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'L';
                check[next] = true;
            }
            int bottom = x % 10;
            next = (x / 10) + (bottom * 1000);
            if (!check[next]) {
                q.push(next);
                dist[next] = dist[x] + 'R';
                check[next] = true;
            }
        }
        cout << dist[end] << '\n';
    }
    return 0;
}

에라토스테네스의 체 - (소수 구하기)

소수를 구하는 알고리즘 중에 가장 유명한 Algorithm

아리스토텔레스 형의 친구 에라토스테네스의 체이다.

바로 본론으로 들어가서 소스코드 함 봐보자.

그냥 평범하게 2중 for문을 통해 구할 수도 있지만, 구해야 하는 소수의 자릿수가 커지면 시간초과가 떠버릴 것이다.

그래서 간단한 if문을 더해주어 2중 for문이지만, O(N)과 같은 시간복잡도를 낼 수 있다리.

이거는 수학자들에 의해 이미 증명된 공식을 사용한 것인데.

소수는 n의 배수가 아니어야 한다.

입력받은 수를 입력받은 수보다 작은 수 들로 나누어서 떨어지면 소수가 아니다.

그러나 모두 나누어볼 필요없이, 루트 n 까지만 나누어서 떨어지면 소수가 아니다.

이 소스코드는 1000 이하의 소수를 구하는 놈이다리.

소스 코드

 
x
#include<iostream>
​
using namespace std;
​
int main()
{
    int arr[1001] = {0};
    for(int i=2;i<=1000;i++)
        arr[i] = i;
    for(int i=2;i<=1000;i++)
    {
        if(!arr[i]) continue;
        for(int j = i*2; j <=1000; j+=i)
            arr[j] = 0;
    }
    
    for(int i=2;i<=1000;i++)
    {
        if(arr[i]) cout << arr[i] << ' ';
    }
    
    return 0;
}

완전탐색 - 순열 응용편 (차이를 최대로 - 10819번 , 외판원 순회 2 - 10971번 , 로또 - 6603번)

완전 탐색을 순열을 이용하여 문제를 한번 기똥차게 풀어보자

일단 순열의 시간 복잡도는 O(N!) 이라는 것을 알자!

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

1) 차이를 최대로 - 10819번

주어진 정수의 숫자들의 순서를 순열(next_permutation)을 통해 구하고, 조건문을 통해 가장 큰 값을 구합시드아. 근데 여기서 주의할 점은 처음부터 쫘르르르르륵 구해야 하기 때문에, 그냥 주어진 입력에서 순열을 돌리는 것이아니라, 정렬(sort)을 한다음에 돌려야 처음부터 끝까지 도는 것이다.

문제

N개의 정수로 이루어진 배열 A가 주어진다. 이 때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최대값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

입력

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

예제 입력

 
x
6
20 1 15 8 4 10

예제 출력

 
62

소스 코드

 
​x
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int main()
{
    int t;
    vector<int> v;
    int res = 0;
    cin >> t;
    for(int i=0;i<t;i++)
    {
        int tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    
    sort(v.begin(), v.end());
    
    do{
        int tmp = 0;
        for(int i=0;i<v.size() - 1;i++)
            tmp += abs(v[i] - v[i+1]);
        if(res < tmp)
            res = tmp;
    }while(next_permutation(v.begin(), v.end()));
    
    cout << res << '\n';
    
    return 0;
}
​

2) 외판원 순회 2 - 10971번

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

순열을 이용하여 처음부터 끝까지 모든 경우의 수를 구한다음 , for문을 이용하여 완전 탐색하는 문제

문제

외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

각 도시간에 이동하는데 드는 비용은 행렬 W[i,j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i,j] 는 W[j,i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i,i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i,j]=0이라고 하자.

N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 도시의 수 N이 주어진다. (2<=N<=10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i,j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력

 
xxxxxxxxxx
4
0 10 15 20
5  0  9 10
6 13  0 12
8  8  9  0

예제 출력

 
xxxxxxxxxx
35

소스 코드

 
x
#include<iostream>
#include<algorithm>
#include<vector>
​
using namespace std;
​
int main()
{
    int n , res = 987654321;
    cin >> n;
    vector<vector<int>> v(n+1,vector<int>(n+1,0));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
            cin >> v[i][j];
    }
    
    vector<int> tmp(n+1);
    for(int i=1;i<=n;i++)
        tmp[i] = i;
    
    do{
        int len = 0;
        int chk = 0;
        for(int i=1;i<=tmp.size() - 2;i++)
        {
            len += v[tmp[i]][tmp[i+1]];
            if(!v[tmp[i]][tmp[i+1]]) chk = 1;
        }
        len += v[tmp[4]][tmp[1]];
        if(!v[tmp[4]][tmp[1]]) chk = 1;
        if(res > len && chk == 0)
            res = len;
    }while(next_permutation(tmp.begin(), tmp.end()));
    
    cout << res << '\n';
    
    return 0;
}
​

여기서 시간 복잡도를 줄일 수 있는 방법이 있는데 잘 생각해보면

1 -> 2 -> 3 -> 4 , 2 -> 3 -> 4 -> 1 , 3 -> 4 -> 1 -> 2 , 4 -> 1 -> 2 -> 3

이 네가지는 모든 같은 경우의 수 인걸 알 수 있다. 그래서 첫번째를 제외한 나머지는 의미가 없는 연산이 된다. 그래서 시작 위치를 고정 시켜도 상관이 없는데 , 1의 위치를 고정 시켜버리자(순열의 갯수가 1줄어듬 , factorial 기준으로는 엄청나게 효과적인 방법)

while(next_permutation(tmp.begin(), tmp.end())); 이 부분을

while(next_permutation(tmp.begin() + 1, tmp.end())); 이걸로 수정 하면 같은 결과를 가지면서 더 욱 빠른 알고리즘이 된다.

3) 로또 - 6603번

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

이 문제에서 아주 좋은 스킬 하나 배울 수 있다 생각한다.

예를 들어 7개의 숫자가 있는데, 이중 내가 6개의 숫자를 골라야 한다.소스를 통해 확인해보자

아! 일단 여기서 알아야 할게 순열은 중복되는 것은 걸러버린다. 예를 들어 설명하면

d 라는 벡터에 [0] = 0, [1] = 1, [2] = 1, [3] = 1, [4] = 1 , [6] = 1; 이 있고, 순열을 돌리면

0 1 1 1 1 1 1

1 0 1 1 1 1 1

1 1 0 1 1 1 1

1 1 1 0 1 1 1

1 1 1 1 0 1 1

1 1 1 1 1 0 1

1 1 1 1 1 1 0 요로코롬 중복을 제외되면서 출력된다.

문제

독일 로또는 {1, 2, ..., 49}에서 숫자 6개를 고른다.

로또 번호를 선택하는데 사용되는 가장 유명한 전략은 49가지 숫자 중 k(k>6)개의 숫자를 골라 집합 S를 만든 다음 그 숫자만 가지고 번호를 선택하는 것이다.

예를 들어, k=8, S={1,2,3,5,8,13,21,34}인 경우 이 집합 S에서 숫자를 고를 수 있는 경우의 수는 총 28가지이다. ([1,2,3,5,8,13], [1,2,3,5,8,21], [1,2,3,5,8,34], [1,2,3,5,13,21], ..., [3,5,8,13,21,34])

집합 S와 k가 주어졌을 때, 숫자를 고르는 모든 방법을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 숫자는 k (6 < k < 13)이고, 다음 k개 숫자는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 주어진다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스 마다 숫자를 고르는 모든 방법을 출력한다. 이 때, 사전 순으로 출력한다.

각 테스트 케이스 사이에는 빈 줄을 하나 출력한다.

예제 입력

 
xxxxxxxxxx
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0

예제 출력

 
xxxxxxxxxx
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
​
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
​
using namespace std;
​
int main()
{
    while(1)
    {
        int n;
        cin >> n;
        if(!n) break;
        vector<int> v;
        for(int i=0;i<n;i++)
        {
            int tmp;
            cin >> tmp;
            v.push_back(tmp);
        }
        
        vector<int> d;
        for(int i=1;i<=n-6;i++)
            d.push_back(0);
        for(int i=1;i<=6;i++)
            d.push_back(1);
        
        vector<vector<int>> res;
        do{
            vector<int> tmp;
            for(int i=0;i<n;i++)
                if(d[i]) tmp.push_back(v[i]);
            res.push_back(tmp);
        }while(next_permutation(d.begin(), d.end()));
        
        sort(res.begin(),res.end());
        
        for(int i=0;i<res.size();i++)
        {
            for(int j =0;j<res[i].size();j++)
                cout << res[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}
​

완전탐색 - 순열 기초

C++ STL의 알고리즘의 next_permutation 과 prev_permutation을 활용하여 완전탐색 문제에 응용해봅시다.

순열을 연습해보자

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

문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력 1 복사

 
3

예제 출력 1 복사

 
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

소스 코드

 
#include<iostream>
#include<algorithm>
#include<vector>
​
using namespace std;
​
int main()
{
    vector<int> v;
    int n;
    cin >> n;
    for(int i=1;i<=n;i++)
        v.push_back(i);
    
    do{
        for(int i=0;i<v.size();i++)
            cout << v[i] << ' ';
        cout << '\n';
    }while(next_permutation(v.begin(), v.end()));
    
    return 0;
}