띠그랭

삼성 코딩 테스트 기출 - 톱니바퀴 14891번

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

17:31 시작 —> 19:20 종료

이 문제는 정말... 톱니바퀴를 미리 돌리면 안되는데, rotate 함수를 미리 돌려서 문제를 틀렸다..

그래서 기준이 되는 놈을 맨 마지막에 rotate를 했는데, 이렇게 하니 테스트케이스가 다 맞게 나왔다..

하지만 이거슨 함정.. 기준이 되는 놈말고도 나머지도 check를 한담에 마지막에 한꺼번에 rotate를 해야하는데, 테스트케이스가 맞게 나오니 여기서 멘붕이 와서 찾는데 정말 오래 걸렸다.

너무 안풀려서 도중에 한번 쏵다 지웠다가 마음을 비우고 처음부터 다시 짰는데, 이러니 좀 술술 코드가 짜이더니 맞아부렸다. 와 이 문제 나왔었으면 진짜 클일 날뻔.. 단순 구현 문제같은데 이런거에 너무 약한거 같다 미띤..

문제

총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.

이 때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.

톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.

두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.

위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.

톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나있다.

다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.

출력

총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.

• 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
• 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
• 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
• 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점

예제 입력 1

 
xxxxxxxxxx
10101111
01111101
11001110
00000010
2
3 -1
1 1

예제 출력 1

 
xxxxxxxxxx
7

예제 입력 2

 
xxxxxxxxxx
11111111
11111111
11111111
11111111
3
1 1
2 1
3 1

예제 출력 2

 
xxxxxxxxxx
15

예제 입력 3

 
xxxxxxxxxx
10001011
10000011
01011011
00111101
5
1 1
2 1
3 1
4 1
1 -1

예제 출력 3

 
xxxxxxxxxx
6

예제 입력 4

 
xxxxxxxxxx
10010011
01010011
11100011
01010101
8
1 1
2 1
3 1
4 1
1 -1
2 -1
3 -1
4 -1

예제 출력 4

 
5

소스 코드

 
xxxxxxxxxx
#include<iostream>
#include<queue>
#include<algorithm>
#include<string>
#include<math.h>
using namespace std;
​
vector<vector<int>> tobny(5, vector<int>(8, 0));
int command;
queue<pair<int, int>> q;
int result;
void input()
{
    for (int i = 1; i <= 4; i++)
    {
        string s;
        cin >> s;
        for (int j = 0; j < s.size(); j++)
            tobny[i][j] = s[j] - '0';
    }
    cin >> command;
    for (int i = 0; i < command; i++)
    {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        q.push({ tmp1,tmp2 });
    }
}
​
int engine1(int n1,int n2,int dir)  // 왼쪽 용 엔진
{
    if (dir == 1)       // 기준 톱니(n1)가 시계방향
    {
        if (tobny[n1][6] != tobny[n2][2])   // 둘다 돌아갈 때
            return 1;
        else  // 기준 톱니(n1)만 돌아갈 때
            return 0;
    }
    else
    {
        if (tobny[n1][6] != tobny[n2][2])   // 둘다 돌아갈 때
            return 1;
        else  // 기준 톱니(n1)만 돌아갈 때
            return 0;
    }
}
​
int engine2(int n1, int n2, int dir)    // 오른쪽 용 엔진
{
    if (dir == 1)   // 기준 톱니(n1)가 시계방향
    {
        if (tobny[n1][2] != tobny[n2][6])   // 둘다 돌아갈 때
            return 1;
        
        else  // 기준 톱니(n1)만 돌아갈 때
            return 0;
    }
    else
    {
        if (tobny[n1][2] != tobny[n2][6])   // 둘다 돌아갈 때
            return 1;
        
        else  // 기준 톱니(n1)만 돌아갈 때
            return 0;
        
    }
}
​
int main()
{
    input();
​
    for (int i = 0; i < command; i++)
    {
        while (1)
        {
            int rot[5] = {0};
            if (q.empty()) break;
            int here_tobny = q.front().first;
            int here_dir = q.front().second;
            q.pop();
            // 왼쪽 돌리기
            
            int tmp_left_dir = here_dir;
            for (int i = here_tobny; i > 1; i--)
            {
                int chk = engine1(i, i - 1, tmp_left_dir);
                if (!chk) break;
                tmp_left_dir *= -1;
                rot[i - 1] = tmp_left_dir;
            }
​
            // 오른쪽 돌리기
            int tmp_right_dir = here_dir;
            for (int i = here_tobny; i < 4; i++)
            {
                int chk = engine2(i, i + 1, tmp_right_dir);
                if (!chk) break;
                tmp_right_dir *= -1;
                rot[i + 1] = tmp_right_dir;
            }
​
            for (int i = 1; i <= 4; i++)
            {
                if(rot[i] == 1)
                    rotate(tobny[i].begin(), tobny[i].begin() + 7, tobny[i].end());
                else if(rot[i] == -1)
                    rotate(tobny[i].begin(), tobny[i].begin() + 1, tobny[i].end());
            }
​
            if(here_dir == 1)
                rotate(tobny[here_tobny].begin(), tobny[here_tobny].begin() + 7, tobny[here_tobny].end());
            else
                rotate(tobny[here_tobny].begin(), tobny[here_tobny].begin() + 1, tobny[here_tobny].end());
        }
    }
​
    for (int i = 1; i <= 4; i++)    // 점수 계산
    {
        if (tobny[i][0] == 1)
            result += pow(2, i - 1);
    }
​
    cout << result << '\n';
​
    return 0;
}

삼성 코딩 테스트 기출 - 경사로 14890번

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

15 : 46 시작 —> 16:55 종료

와.. 이건 내가 푸는데 코드가 무진장 더러웠다. 하나씩 차근차근 조건 주면서 문제를 풀었는데

가로, 세로 따로 검사 하는걸 한번에 하려니깐, 잘 안되서 가로 용 함수, 세로 용 함수 를 나눠서 짜니까

코드의 양이 너무너무너무너무 길게 나왔다.

문제

크기가 N×N인 지도가 있다. 지도의 각 칸에는 그 곳의 높이가 적혀져 있다.

오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.

다음과 같은 N=6인 경우 지도를 살펴보자.

이 때, 길은 총 2N개가 있으며, 아래와 같다.

길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.

• 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
• 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
• 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.

아래와 같은 경우에는 경사로를 놓을 수 없다.

• 경사로를 놓은 곳에 또 경사로를 놓는 경우
• 낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
• 낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
• 경사로를 놓다가 범위를 벗어나는 경우

L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.

경사로를 놓을 수 없는 경우는 아래와 같다.

위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.

가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 초록색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.

지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.

출력

첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.

예제 입력 1

 
xxxxxxxxxx
6 2
3 3 3 3 3 3
2 3 3 3 3 3
2 2 2 3 2 3
1 1 1 2 2 2
1 1 1 3 3 1
1 1 2 3 3 2

예제 출력 1

 
xxxxxxxxxx
3

예제 입력 2

 
xxxxxxxxxx
6 2
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 2

 
xxxxxxxxxx
7

예제 입력 3

 
xxxxxxxxxx
6 3
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 3

 
xxxxxxxxxx
3

예제 입력 4

 
xxxxxxxxxx
6 1
3 2 1 1 2 3
3 2 2 1 2 3
3 2 2 2 3 3
3 3 3 3 3 3
3 3 3 3 2 2
3 3 3 3 2 2

예제 출력 4

 
11 

소스 코드

 
x
#include<iostream>
​
using namespace std;
​
int N, L;   // 길의 수 : N , 경사로 길이 : L
int map[101][101];  // 맵 저장
int res;            // 결과 값 저장
int chk1[101][101]; // 경사로를 중복놓는 걸 방지하기 위한 chk배열 (세로용)
int chk2[101][101]; // 경사로를 중복놓는 걸 방지하기 위한 chk배열 (가로용)
void input()
{
    cin >> N >> L;
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
            cin >> map[i][j];
    }
}
​
int check1(int sw, int y, int x)    // 경사로를 놓을 수 있는지 검사 (세로용)
{
    if (sw == 0)    // 현재 위치가 높이가 클 때
    {
        if (map[y][x] - 1 != map[y + 1][x]) return 0;
​
        for (int i = 1; i <= L; i++)    // 이미 경사로가 놓여져 있는지 검사
        {
            if (chk1[y + i][x]) return 0;
        }
​
        for (int i = 1; i <= L; i++)
        {
            if (y + i > N) return 0;
            if (map[y + 1][x] != map[y + i][x]) return 0;
        }
​
        for (int i = 1; i <= L; i++)
            chk1[y + i][x] = 1;
​
        return 1;
    }
    else if (sw == 1)       // 현재 위치가 낮을 때
    {
        if (map[y][x] + 1 != map[y + 1][x]) return 0;
​
        for (int i = 0; i < L; i++)     // 이미 경사로가 놓여져 있는지 검사
        {
            if (chk1[y - i][x]) return 0;
        }
​
        for (int i = 0; i < L; i++)
        {
            if (y - i < 1) return 0;
            if (map[y][x] != map[y - i][x]) return 0;
        }
​
        for (int i = 0; i < L; i++)
            chk1[y - i][x] = 1;
​
        return 1;
    }
}
​
int check2(int sw,int y,int x)      // 경사로를 놓을 수 있는지 검사 (가로용)
{
    if (sw == 0)    // 현재 위치가 높이가 클 때
    {
        if (map[y][x] - 1 != map[y][x + 1]) return 0;
​
        for (int i = 1; i <= L; i++)    // 이미 경사로가 놓여져 있는지 검사
        {
            if (chk2[y][x + i]) return 0;
        }
​
        for (int i = 1; i <= L; i++)
        {
            if (x + i > N) return 0;
            if (map[y][x + 1] != map[y][x + i]) return 0;
        }
​
        for (int i = 1; i <= L; i++)
            chk2[y][x + i] = 1;
​
        return 1;
    }
    else if (sw == 1)       // 현재 위치가 낮을 때
    {
        if (map[y][x] + 1 != map[y][x + 1]) return 0;
​
        for (int i = 0; i < L; i++)     // 이미 경사로가 놓여져 있는지 검사
        {
            if (chk2[y][x - i]) return 0;
        }
​
        for (int i = 0; i < L; i++)
        {
            if (x - i < 1) return 0;
            if (map[y][x] != map[y][x - i]) return 0;
        }
​
        for (int i = 0; i < L; i++)
            chk2[y][x - i] = 1;
​
        return 1;
    }
}
​
int Row_road_check(int n)   // 가로 길 검사하기
{
    for (int i = 1; i < N; i++)
    {
        if (map[n][i] == map[n][i + 1]) continue;
        else if (map[n][i] != map[n][i + 1])    // 길의 높이가 다를 때
        {
            if (map[n][i] > map[n][i + 1])      // 현재 길의 높이가 높을 때
            {
                if (check2(0, n, i)) continue;
                return 0;
            }
            else  // 현재 길 보다 다음 길의 높이가 더 높을 때 
            {
                if (check2(1, n, i)) continue;
                return 0;
            }
        }
    }
    return 1;
}
​
int Col_road_check(int n)   // 세로 길 검사하기
{
    for (int i = 1; i < N; i++)     
    {
        if (map[i][n] == map[i + 1][n]) continue;
        else if (map[i][n] != map[i + 1][n])    // 길의 높이가 다를 때
        {
            if (map[i][n] > map[i + 1][n])      // 현재 길의 높이가 높을 때
            {
                if (check1(0, i, n)) continue;
                return 0;
            }
            else  // 현재 길 보다 다음 길의 높이가 더 높을 때 
            {
                if (check1(1, i, n)) continue;
                return 0;
            }
        }
    }
    return 1;
}
​
int main()
{
    input();
    for (int i = 1; i <= N; i++)    // 각 줄 검사
    {
        if (Row_road_check(i)) res++;   // 가로 줄 검사
        if (Col_road_check(i)) res++;   // 세로 줄 검사
    }
    cout << res << '\n';
    return 0;
}

삼성 코딩 테스트 기출 - 스타트와 링크 - 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;
}
​