띠그랭

삼성 코딩 테스트 기출 - 로봇청소기 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;
}

완전탐색 - 순열 응용편 (차이를 최대로 - 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;
}

완전 탐색 - Brute Force Search

일단 완전 탐색을 할 수 있는 방법은 여러가지가 있는데,

1) Brute Force - 그냥 다 해보리기

2) BFS - 그래프로 표현하여 다 탐색하기

3) 재귀

4) 비트마스크

5) 순열

6) 백트래킹

등등 이 있다.

Brute Force

그냥 다 검색해보는 Brute Force를 공부해보자아.

for문과 if문을 이용하여 처음부터 쭈루룩 탐색해보는 방법.

여기서 중요한 것은 범위, 무작정 다 검색하기 때문에 시간초과가 날수 있다.

for문 1억번을 1초라고 보통 생각하기 때문에 이걸 잘 생각하며 풀어야 한다.

쉬운 문제로 일단 어떤 느낌인지 공부를 해보면

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

날짜 계산 1476번

이 문제는 for문 과 간단한 if문을 통해 1, 1 , 1부터 쭈루룩 돌아서 입력과 같은 값이 되었을 때 count한 값을 출력하는 심플한 문제

문제

준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다.

지구를 나타내는 숫자를 E, 태양을 나타내는 숫자를 S, 달을 나타내는 숫자를 M이라고 했을 때, 이 세 수는 서로 다른 범위를 가진다. (1 ≤ E ≤ 15, 1 ≤ S ≤ 28, 1 ≤ M ≤ 19)

우리가 알고있는 1년은 준규가 살고있는 나라에서는 1 1 1로 나타낼 수 있다. 1년이 지날 때마다, 세 수는 모두 1씩 증가한다. 만약, 어떤 수가 범위를 넘어가는 경우에는 1이 된다.

예를 들어, 15년은 15 15 15로 나타낼 수 있다. 하지만, 1년이 지나서 16년이 지나면 16 16 16이 아니라 1 16 16이 된다. 이유는 1 ≤ E ≤ 15 라서 범위를 넘어가기 때문이다.

E, S, M이 주어졌고, 1년이 준규가 사는 나라에서 1 1 1일때, 준규가 사는 나라에서 E S M이 우리가 알고 있는 연도로 몇 년인지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 세 수 E, S, M이 주어진다. 문제에 나와있는 범위를 지키는 입력만 주어진다.

출력

첫째 줄에 E S M으로 표시되는 가장 빠른 연도를 출력한다. 1 1 1은 항상 1이기 때문에, 정답이 음수가 나오는 경우는 없다.

예제 입력 1

 
xxxxxxxxxx
1 16 16

예제 출력 1

 
xxxxxxxxxx
16

예제 입력 2

 
xxxxxxxxxx
1 1 1

예제 출력 2

 
xxxxxxxxxx
1

예제 입력 3

 
xxxxxxxxxx
1 2 3

예제 출력 3

 
xxxxxxxxxx
5266

소스 코드

 
xxxxxxxxxx
#include<iostream>
using namespace std;
int main()
{
    // 날짜 계산 1476번
    int E, S, M;
    int e = 1, s = 1, m = 1;
    int year = 1;
    cin >> E >> S >> M;
    while (!(E == e && S == s && M == m))
    {
        e++;
        s++;
        m++;
        if (e == 16) e = 1;
        if (s == 29) s = 1;
        if (m == 20) m = 1;
        year++;
    }
    cout << year << '\n';
    return 0;
}

리모콘 1107번

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

문제

수빈이는 TV를 보고 있다. 수빈이는 채널을 돌리려고 했지만, 버튼을 너무 세게 누르는 바람에, 일부 숫자 버튼이 고장났다.

리모컨에는 버튼이 0부터 9까지 숫자, +와 -가 있다. +를 누르면 현재 보고있는 채널에서 +1된 채널로 이동하고, -를 누르면 -1된 채널로 이동한다. 채널 0에서 -를 누른 경우에는 채널이 변하지 않고, 채널은 무한대 만큼 있다.

수빈이가 지금 이동하려고 하는 채널은 N이다. 어떤 버튼이 고장났는지 주어졌을 때, 채널 N으로 이동하기 위해서 버튼을 최소 몇 번 눌러야하는지 구하는 프로그램을 작성하시오.

수빈이가 지금 보고 있는 채널은 100번이다.

입력

첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼이 주어지며, 같은 버튼이 중복되서 주어지는 경우는 없다.

출력

첫째 줄에 채널 N으로 이동하기 위해 버튼을 최소 몇 번 눌러야 하는지를 출력한다.

예제 입력 1

 
xxxxxxxxxx
5457
3
6 7 8

예제 출력 1

 
xxxxxxxxxx
6

예제 입력 2

 
xxxxxxxxxx
100
5
0 1 2 3 4

예제 출력 2

 
xxxxxxxxxx
0

예제 입력 3

 
xxxxxxxxxx
500000
8
0 2 3 4 6 7 8 9

예제 출력

 
xxxxxxxxxx
11117

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
vector<int> v(10);
int res;
​
int check(int c)
{
    int len = 0;
    if(c == 0)
    {
        if(v[0]) return 0;
        else return 1;
    }
    
    while(c > 0)
    {
        if(v[c % 10]) return 0;
        len++;
        c /= 10;
    }
    return len;
}
​
int main()
{
    int c;
    int n;
    cin >> c;
    cin >> n;
    for(int i=0;i<n;i++)
    {
        int tmp;
        cin >> tmp;
        v[tmp] = 1;
    }
    
    res = abs(c - 100);
    
    
    for(int i=0;i<=1000000;i++)
    {
        int len = check(i);
        if(len > 0)
        {
            int press = abs(c - i);
            if(res > len + press)
                res = len + press;
        }
    }
    
    cout << res << '\n';
    
    return 0;
}
​

완전 탐색 - 비트마스크

비트 연산

shift left (<<) , shift right (>>) 두개의 연산이 있다

A >> B (A 를 오른쪽으로 B비트만큼 이동)

1 >> 1 0(이진법)

10 >> 1 101(이진법)

10 >> 2 1010 을 오른쪽으로 2비트 이동 ==> 10 즉 2가 됨

A << B 는 A * 2^B

A >> B 는 A / 2^B

이것을 이용하여 할 수 있는 것은 정수를 통해 집합을 표현할 수 있다.

만약 10명의 학생이 있고, 0~9번 이라는 번호로 학생을 표현하고 싶을 때 1,3,5,7,9 번의 학생을 한 집합으로 표현한다면,

이런 식으로 표현이 가능하며, 2진법으로 표현한다면 1010101010(2) 으로 표현할 수 있다.

만약에 내가 5번 학생이 있는걸 확인하고 싶으면

 
xxxxxxxxxx
int sum = 682;
if(sum & (1 << 5)) cout << "5번 학생이 있다" << '\n';

이 집합 상태에서 어느 한 학생을 추가(삽입) 하고싶다면 OR(|) 연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum | (1 << 2);   // 2번 학생을 추가

여기서 + 연산을 사용하지 않은 이유는 carry가 발생하여, 다른 값에 영향을 줄수 있기 때문에 OR연산을 사용한다.

집합에서 어느 한 학생을 제거(삭제) 하고 싶다면 N0T(&)연산을 이용하면 된다.

 
xxxxxxxxxx
sum = sum & ~(1 << 5);  // 5번 학생을 제거

전체 집합 표현

공집합

A라는 집합에서 특정 n 을 추가 할때

A | (1 << n)

A라는 집합에서 특정 n 을 확인 할때

A & (1 << n)

A라는 집합에서 특정 n 을 제거 할때

A & ~(1 << n)

A라는 집합에서 각 값을 토글 할때

A ^ (1 << n)

비트마스크 연산 연습해보기

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

소스 코드

 
x
#include<iostream>
#include<string>
using namespace std;
​
int sum;
​
int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        string ins;
        cin >> ins;
        if(ins == "add")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum | (1 << tmp);
        }
        else if(ins == "remove")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum & ~(1 << tmp);
        }
        else if(ins == "check")
        {
            int tmp;
            cin >> tmp;
            if(sum & (1 << tmp)) cout << "1" << '\n';
            else cout << "0" << '\n';
        }
        else if(ins == "toggle")
        {
            int tmp;
            cin >> tmp;
            tmp--;
            sum = sum ^ (1 << tmp);
        }
        else if(ins == "all")
            sum = (1 << 20) - 1;
        else if(ins == "empty")
            sum = 0;
    }
    return 0;
}

일곱 난쟁이 2309번 - 완탐(순열)

이 문제는 순열을 이용하여 푼 완전탐색 문제이다

9명의 난쟁이들 중에 7명을 고르고 조건을 만족하면 출력하는 문제

vector하나 만들어서 7개의 1과 2개의 0을 넣어 순열 쭈루루룩 돌린담에 조건을 만족하면 출력

이 방법은 next_permutation을 돌리기 전 맨처음 상태도 체크 해야하기 때문에 do_while 사용

문제

왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다. 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다.

아홉 명의 난쟁이는 모두 자신이 "백설 공주와 일곱 난쟁이"의 주인공이라고 주장했다. 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다.

아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오.

입력

아홉 개의 줄에 걸쳐 일곱 난쟁이의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러가지인 경우에는 아무거나 출력한다.

출력

일곱 난쟁이의 키를 오름차순으로 출력한다.

예제 입력

 
xxxxxxxxxx
20
7
23
19
10
15
25
8
13

예제 출력

 
xxxxxxxxxx
7
8
10
13
19
20
23

소스코드

 
xxxxxxxxxx
// 2309번 일곱난쟁이
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
​
vector<int> v(9);
​
void input()
{
 for (int i = 0; i < 9; i++)
  cin >> v[i];
}
​
void DFS()
{
 vector<int> tmp;
​
 for (int i = 0; i < 2; i++)
  tmp.push_back(0);
​
 for (int i = 0; i < 7; i++)
  tmp.push_back(1);
​
 do {
  int sum = 0;
  for (int i = 0; i < tmp.size(); i++)
   if (tmp[i]) sum += v[i];
  if (sum == 100)
   break;
 } while (next_permutation(tmp.begin(), tmp.end()));
​
 vector<int> res;
 for (int i = 0; i < tmp.size(); i++)
 {
  if (tmp[i]) res.push_back(v[i]);
 }
 sort(res.begin(), res.end());
 for (int i = 0; i < res.size(); i++)
  cout << res[i] << '\n';
}
​
int main()
{
 input();
​
 DFS();
​
 return 0;
}

1244번 최대상금 - [S/W 문제해결 응용]

https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15Khn6AN0CFAYD

이 문제는 이중 for문으로 완전탐색을 아주 그냥 돌려버렸다.

중복체크 안하고 돌리면 테스트케이스 7번까지는 돌아간다.

하지만 테스트케이스 8번부터 시간초과가 나버린다.

그러므로 중복체크 해야하므니다.

소스코드

 
xxxxxxxxxx
// 1244 최대상금 - 완탐
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
​
int T, seq;
vector<int> v;
int max_price;
int check[1000000][11];
​
int calc()
{
    int tmp = 0;
    for (int i = 0; i < v.size(); i++)
        tmp += (v[i] * pow(10, v.size() - i - 1));
    
    return tmp;
}
​
void swap(int f,int s)
{
    int first = v[f];
    int second = v[s];
    v[f] = second, v[s] = first;
}
​
void DFS(int n)
{
    if (n >= seq)
    {
        max_price = max(max_price, calc());
        return;
    }
​
    if (check[calc()][n]) return;       // 이 두줄이 중복체크용
    check[calc()][n] = 1;
​
    for (int i = 0; i < v.size(); i++)
    {
        for (int j = i+1; j < v.size(); j++)
        {
            swap(i, j);
            DFS(n + 1);
            swap(i, j);
        }
    }
}
​
void input()
{
    cin >> T;
    for (int i = 1; i <= T; i++)
    {
        string tmp;
        cin >> tmp >> seq;
        for (int j = 0; j < tmp.size(); j++)
            v.push_back(tmp[j] - '0');
        DFS(0);
        cout << "#" << i << " " << max_price;
        max_price = 0;
        v.clear();
    }
}
​
int main()
{
    input();
    
    return 0;
}

로또 6603번 (완전탐색-순열)

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

algorithm에 있는 순열함수인 next_permutation을 이용하여

만약 7개 중에 6개를 골라야한다면, 배열에 0을 1개 , 1을 6개 넣어서 나올수 있는 모든 순열을 쫘르르륵 한다음에 1이 위치하고있는 인덱스를 활용하면, 7가지 숫자중 6개의 모든 조합을 추출할 수 있다. 말로는 이해하기 어려울수 있으니 소스를 참고바람.

문제

독일 로또는 {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()
{
    int k;
    while (cin >> k)
    {
        if (k == 0) break;
        vector<int> v(k);
        for (int i = 0; i < k; i++)
            cin >> v[i];
​
        vector<int> d(k);
        for (int i = 0; i < k - 6; i++)
            d[i] = 0;
        
        for (int i = k - 6; i < k; i++)
            d[i] = 1;
        
        vector<vector<int>> ans;
        do {
            vector<int> current;
            for (int i = 0; i < k; i++)
            {
                if (d[i] == 1)
                    current.push_back(v[i]);
            }
            ans.push_back(current);
        } while (next_permutation(d.begin(), d.end()));
​
        sort(ans.begin(), ans.end());
        
        for (int i = 0; i < ans.size(); i++)
        {
            for (int j = 0; j < ans[i].size(); j++)
                cout << ans[i][j] << ' ';
            cout << '\n';
        }
        cout << '\n';
    }
    return 0;
}