백준 ( 쉽게, 깔끔하게, 시간복잡도가 좋게 )

Chapter 01 그리디

01-1 회의실 배정 ( 1931 )

• 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다
• 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자
• 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다
• 회의의 시작시간과 끝나는 시간이 같을 수도 있다
• 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다

#include<bits/stdc++.h>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int totalmeeting = 0;
    
    int meeting = 0;
    cin>>meeting;
    
    // 미팅 목록을 기록한다 ( 끝나는 시간 기준 정렬을 하기 위해, 끝나는 시간이 앞에 오게 저장한다 )
    vector<pair<int,int>> vMeeting;
    for(int i = 0; i < meeting; ++i)
    {
        int start = 0, end = 0;
        cin>>start>>end;
        vMeeting.push_back(make_pair(end,start));
    }
    sort(vMeeting.begin(), vMeeting.end());
    
    // 마지막 미팅 시간 이후 미팅 목록 중에서 가장 빠른 시간대를 예약한다
    int lastTime = 0;
    for(int i = 0; i < meeting; ++i)
    {
        if(lastTime <= vMeeting[i].second)
        {
            lastTime = vMeeting[i].first;
            totalmeeting = totalmeeting + 1;
        }
    }
    
    cout<<totalmeeting;
    
    return 0;
}

01-2 수 묶기 ( 1744 )

• 수열이 주어졌을 때, 수열의 각 수를 적절히 묶었을 때, 그 합이 최대가 되게 하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int total, onecount, zerocount;
vector<int> positive;
vector<int> negative;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    // 숫자들을 분류한다
    cin >> total;
    for (int i = 0; i < total; i++)
    {
        int value = 0;
        cin >> value;
        if (value > 1) positive.push_back(value);
        else if (value < 0) negative.push_back(value);
        else if (value == 0) zerocount++;
        else onecount++;
    }

    // 자리수를 맞춰준다
    if (positive.size() % 2 == 1)
        positive.push_back(1);
    if (negative.size() % 2 == 1)
    {
        if (zerocount == 0) negative.push_back(1);
        else negative.push_back(0);
    }

    // 양수는 오름차순 음수는 내림차순으로 정렬한다
    sort(positive.begin(), positive.end());
    sort(negative.rbegin(), negative.rend());

    // 두개씩 계산한다
    int sum = onecount;
    for (int i = 0; i < positive.size(); i += 2) 
        sum += positive[i] * positive[i + 1];
    for (int i = 0; i < negative.size(); i += 2)
        sum += negative[i] * negative[i + 1];
    
    cout << sum;
}

01-3 A와 B ( 12904 )

• 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int main()
{
    string S = "", T = "";
    cin>>S;
    cin>>T;
    
    while(true)
    {
        if(T.size() == S.size())
        {
            if(S == T)
            {
                cout << 1 << endl;
                break;
            }
            else
            {
                cout << 0 << endl;
                break;
            }
        }
        
        // 문자열 T를 문자열 S로 역변환해 문제를 해결한다
        if(T[T.size()-1] == 'A')
        {
            T.pop_back();
            continue;
        }
        else if(T[T.size()-1] == 'B')
        {
            T.pop_back();
            reverse(T.begin(), T.end());
            continue;
        }
        
        cout << 0 << endl;
        break;
    }
}

Chapter 02 완전탐색

02-1 테트리스 ( 3019 )

• 블록을 놓는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오

// https://hsdevelopment.tistory.com/506 참고

#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 105;
 
int board[MAX], c, p;
vector<string> v;
 
int simulation(int number)
{
    int ret = 0;
 
    if (number == 1)
    {
        v.push_back("0");
        v.push_back("0000");
    }
    else if (number == 2)
    {
        v.push_back("00");
    }
    else if (number == 3)
    {
        v.push_back("001");
        v.push_back("10");
    }
    else if (number == 4)
    {
        v.push_back("100");
        v.push_back("01");
    }
    else if (number == 5)
    {
        v.push_back("000");
        v.push_back("01");
        v.push_back("101");
        v.push_back("10");
    }
    else if (number == 6)
    {
        v.push_back("000");
        v.push_back("00");
        v.push_back("011");
        v.push_back("20");
    }
    else if (number == 7)
    {
        v.push_back("000");
        v.push_back("02");
        v.push_back("110");
        v.push_back("00");
    }
 
    for (int i = 0; i < v.size(); i++)
    {
        int len = v[i].length();
 
        vector<int> temp;
        for (auto k : v[i])
        {
            temp.push_back(k - '0');
        }
 
        for (int j = 0; j + len <= c; j++)
        {
            bool calc = true;
 
            for (int k = j + 1; k < j + len; k++)
            {
                // board의 모든 구역에 temp를 맞춰봐야 하니까 board수식과 temp 수식이 다르다
                if (board[k] - board[k - 1] != temp[k - j] - temp[k - j - 1])
                {
                    calc = false;
                    break;
                }
            }
            if (calc)
            {
                ++ret;
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    cin >> c >> p;
 
    for (int i = 0; i < c; i++)
    {
        cin >> board[i];
    }
    
    cout << simulation(p) << endl;
    
    return 0;
}

02-2 치킨 배달 ( 15686 )

• 도시의 치킨 거리가 가장 작게 될지 구하는 프로그램을 작성하시오

02-3 동전 게임 ( 9079 )

• 상우는 이것을 최소 횟수의 연산으로 실행하고 싶어한다

02-4 꽃길 ( 14620 )

• 돈이 많지 않은 진아를 위하여 진아가 꽃을 심기 위해 필요한 최소비용을 구해주자

02-5 도영이가 만든 맛있는 음식 ( 2961 )

• 신맛과 쓴맛의 차이가 가장 작은 요리를 만드는 프로그램을 작성하시오

02-6 오목 ( 2615 )

• 아직 승부가 결정되지 않았는지를 판단하는 프로그램을 작성하시오

02-7 링크와 스타트 ( 15661 )

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

02-8 A와 B 2 ( 12919 )

• 주어진 조건을 이용해서 S를 T로 만들 수 있는지 없는지 알아내는 프로그램을 작성하시오

02-9 부분 삼각 수열 ( 1548 )

• 삼각 수열의 최대 길이를 구하는 프로그램을 작성하시오

02-10 제곱수 찾기 ( 1025 )

• 연두가 만들 수 있는 정수 중에서 가장 큰 완전 제곱수를 구해보자 완전 제곱수란 어떤 정수를 제곱한 수이다

Chapter 03 DFS와 백트래킹

03-1 테크노미노 ( 14500 )

• 테트로미노는 반드시 한 정사각형이 정확히 하나의 칸을 포함하도록 놓아야 하며, 회전이나 대칭을 시켜도 된다

// https://9967han.tistory.com/15 참고

#include<bits/stdc++.h>
using namespace std;

const int MAX = 501;

int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};
int N, M, ans = 0;

void getMaxNum(vector<vector<int>>& mymap, vector<vector<bool>>& visited, int x, int y, int cnt, int curScore)
{
    // 블록이 4개라면 스코어 갱신이 가능한지 체크
    if(cnt == 4)
    {
        if(ans < curScore) ans = curScore;
        return;
    }

    // 현재 노드에서 만들수 있는 모든 도형을 만들자
    for(int i = 0; i < 4; ++i)
    {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if(nx < 0 || ny < 0 || ny >= N || nx >= M || visited[ny][nx]) continue;
        visited[ny][nx] = true;
        getMaxNum(mymap, visited, nx, ny, cnt + 1, curScore + mymap[ny][nx]);
        visited[ny][nx] = false;
    }
}

int main()
{
    vector<vector<int>> mymap(MAX, vector<int>(MAX, 0));
    vector<vector<bool>> visited(MAX, vector<bool>(MAX, false));
 
    cin >> N >> M;

    for(int y = 0; y < N; ++y)
    {
        for(int x = 0; x < M; ++x)
        {
            cin >> mymap[y][x];
        }
    }

    for(int y = 0; y < N; ++y)
    {
        for(int x = 0; x < M; ++x)
        {
            // 모든 노드를 방문한다
            visited[y][x] = true;
            getMaxNum(mymap, visited, x, y, 1, mymap[y][x]);
            visited[y][x] = false;
            
            // ㅏ ㅓ ㅗ ㅜ 를 만들자
            if(y-1 >= 0 && x+1 < M && y+1 < N) //ㅏ ( ㅏ 같은 경우는 x-1 >= 0 이라는 조건이 있으면 안된다는 것을 명심하자 )
            {
                ans = max(ans, (mymap[y-1][x] + mymap[y][x] + mymap[y][x+1] + mymap[y+1][x]));
            }
            if(x-1 >= 0 && y-1 >= 0 && y+1 < N) //ㅓ
            {
                ans = max(ans, (mymap[y-1][x] + mymap[y][x] + mymap[y][x-1] + mymap[y+1][x]));
            }
            if(x-1 >= 0 && y-1 >= 0 && x+1 < M) //ㅗ
            {
                ans = max(ans, (mymap[y-1][x] + mymap[y][x] + mymap[y][x-1] + mymap[y][x+1]));
            }
            if(x-1 >= 0 && x+1 < M && y+1 < N) //ㅜ
            {
                ans = max(ans, (mymap[y][x] + mymap[y][x-1] + mymap[y][x+1] + mymap[y+1][x]));
            }
        }
    }

    cout << ans;
}

03-2 무기 공학 ( 18430 )

• 길동이가 만들 수 있는 부메랑들의 강도 합의 최댓값을 출력하는 프로그램을 작성하시오

// 백트래킹

03-3 파이프 옮기기 1 ( 17070 )

• 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<vector<int>>& visited, int y, int x, int dir, int housecount)
{
    visited[y][x] = visited[y][x] + 1;
    
    // 경로 1
    if(dir == 0 || dir == 2)
    {
        if(x < housecount && visited[y][x+1] != -1)
        {
            dfs(visited, y, x+1, 0, housecount);
        }
    }
    // 경로 2
    if(dir == 1 || dir == 2)
    {
        if(y < housecount && visited[y+1][x] != -1)
        {
            dfs(visited, y+1, x, 1, housecount);
        }
    }
    // 경로 3
    if(x < housecount && y < housecount && visited[y][x+1] != -1 && visited[y+1][x] != -1 && visited[y+1][x+1] != -1)
    {
        dfs(visited, y+1, x+1, 2, housecount);
    }
    
    return;
}

int main()
{
    int housecount = 0;
    cin >> housecount;
    
    // https://leeeegun.tistory.com/m/3 참고
    vector<vector<int>> visited(housecount+1, vector<int>(housecount+1, false));
    
    for(int i = 1; i <= housecount; i++)
    for(int j = 1; j <= housecount; j++)
    {
        int value = 0;
        cin >> value;

        if(value == 0)
        {
            visited[i][j] = 0;
        }
        else
        {
            visited[i][j] = -1;
        }
    }
    
    dfs(visited, 1, 2, 0, housecount);
    
    if(visited[housecount][housecount] != -1) cout << visited[housecount][housecount] << endl;
    else cout << 0 << endl;
}

03-4 넴모넴모 (Easy) ( 14712 )

• 네모가 게임을 그만두었을 때 나올 수 있는 “넴모”의 배치의 가짓수를 구하여라

// 백트래킹

03-5 일곱 난쟁이 ( 2309 )

• 왕비를 피해 일곱 난쟁이들과 함께 평화롭게 생활하고 있던 백설공주에게 위기가 찾아왔다
• 일과를 마치고 돌아온 난쟁이가 일곱 명이 아닌 아홉 명이었던 것이다
• 아홉 명의 난쟁이는 모두 자신이 “백설 공주와 일곱 난쟁이”의 주인공이라고 주장했다
• 뛰어난 수학적 직관력을 가지고 있던 백설공주는, 다행스럽게도 일곱 난쟁이의 키의 합이 100이 됨을 기억해 냈다
• 아홉 난쟁이의 키가 주어졌을 때, 백설공주를 도와 일곱 난쟁이를 찾는 프로그램을 작성하시오

#include <bits/stdc++.h>
using namespace std;

vector<int> vecValue;

void dfs(vector<bool>& visited, int targetcount, int targetsum, int level, int cnt, int sum)
{
    // targetcount에 도달하면 난쟁이 키의 합이 targetsum인지 확인하자
    if(cnt == targetcount)
    {
        if(sum == targetsum)
        {
            for(int i = 0; i < vecValue.size(); ++i)
            {
                if(visited[i] == true)
                    cout << vecValue[i] << endl;
            }
            exit(0);
        }
    }
    
    // 레벨의 끝에 도달했다면 리턴하자
    if(level == vecValue.size())
        return;
    else
    {
        // 레벨의 끝이 아니고 현재 인덱스를 더하는 경우
        visited[level] = true;
        dfs(visited, targetcount, targetsum, level + 1, cnt + 1, sum + vecValue[level]);
        
        // 레벨의 끝이 아니고 현재 인덱스를 더하지 않는 경우
        visited[level] = false;
        dfs(visited, targetcount, targetsum, level+1, cnt, sum);
    }
}

int main(void)
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    for(int i = 0; i < 9;i++)
    {
        int value;
        cin >> value;
        vecValue.push_back(value);
    }
    
    sort(vecValue.begin(), vecValue.end());
    
    vector<bool> visited(vecValue.size());
    dfs(visited, 7, 100, 0, 0, 0);
    
    return 0;
}

03-6 1, 2, 3 더하기 ( 9095 )

• 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오

#include <bits/stdc++.h>
using namespace std;

int answer = 0;

void dfs(int target, int sum)
{
    // 타겟이 맞는지 체크
    if(target <= sum)
    {
        if(target == sum)
        {
            answer++;
        }
        
        return;
    }
    
    // 경로 1
    dfs(target, sum + 1);
    // 경로 2
    dfs(target, sum + 2);
    // 경로 3
    dfs(target, sum + 3);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    int TestCase = 0;
    vector<int> vTestCase;
    cin>>TestCase;
    
    for(int i = 0; i < TestCase; ++i)
    {
        int value = 0;
        cin>>value;
        vTestCase.push_back(value);
    }
    
    for(int i = 0; i < vTestCase.size(); ++i)
    {
        dfs(vTestCase[i], 0);
        cout<<answer<<endl;
        answer = 0;
    }
    
    return 0;
}

03-7 에너지 모으기 ( 16198 )

• N과 에너지 구슬의 무게가 주어졌을 때, 모을 수 있는 에너지 양의 최댓값을 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int max_energe = 0;

void dfs(vector<int> vBall, int erasenumber, int sum_energe)
{
    if(vBall.size() == 2)
    {
        return;
    }
    
    // MAX 에너지 갱신
    int current_energe = sum_energe + (vBall[erasenumber - 1] * vBall[erasenumber + 1]);
    vBall.erase(vBall.begin()+erasenumber);
    if(max_energe <= current_energe)
        max_energe = current_energe;
    
    // 두번째 이후 에너지 구슬 선택
    for(size_t erasenumber = 1; erasenumber < vBall.size() - 1; ++erasenumber)
    {
        dfs(vBall, erasenumber, current_energe);
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    int ball = 0;
    cin >> ball;
    
    vector<int> vBall;
    for(int i = 0; i < ball; ++i)
    {
        int value = 0;
        cin >> value;
        vBall.push_back(value);
    }
    
    // 첫번째 에너지 구슬 선택
    for(size_t erasenumber = 1; erasenumber < ball - 1; ++erasenumber)
    {
        dfs(vBall, erasenumber, 0);
    }
    
    cout << max_energe << endl;
    
    return 0;
}

03-8 암호 만들기 ( 1759 )

• 가능성 있는 암호들을 모두 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

void dfs(vector<char> vChar, int L, int C, int length, int level, string curstr)
{
	// 문자열 길이 체크
	if (length == L)
	{
		int mo = 0, ja = 0;
		for (int i = 0; i < L; ++i)
		{
			if (curstr[i] == 'a' || curstr[i] == 'e' || curstr[i] == 'i' || curstr[i] == 'o' || curstr[i] == 'u')
				mo++;
			else
				ja++;
		}

		if (1 <= mo && 2 <= ja)
			cout << curstr << endl;

		return;
	}

	// 레벨의 끝에 도달했다면 리턴하자
	if (level == C)
	{
		return;
	}
	else
	{
		// 문자열을 추가해주는 경우
		dfs(vChar, L, C, length + 1, level + 1, curstr + vChar[level]);
		// 문자열을 추가해주지 않는 경우
		dfs(vChar, L, C, length, level + 1, curstr);
	}
}

int main()
{
	int L = 0, C = 0;
	cin >> L >> C;

	vector<char> vChar;
	for (int i = 0; i < C; ++i)
	{
		char value;
		cin >> value;
		vChar.push_back(value);
	}

	sort(vChar.begin(), vChar.end());

	dfs(vChar, L, C, 0, 0, "");

	return 0;
}

03-9 N과 M (1) (15649)

• 자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오

// 백트래킹 유형
#include<bits/stdc++.h>
using namespace std;

#define MAX 9

int N, M;
int arr[MAX];
bool visited[MAX];

void dfs(int count)
{
    if(count == M)
    {
        for(auto i = 0; i < M; ++i)
            cout << arr[i] << " ";
        cout << '\n';
    }
    else
    {
        for(auto i = 1; i <= N; ++i)
        {
            if(!visited[i])
            {
                visited[i] = true;
                arr[count] = i;
                dfs(count + 1);
                visited[i] = false;
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> N >> M;
    dfs(0);
}

03-10 쿼드트리 ( 1992 )

• 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오

Chapter 04 BFS

04-1 뱀과 사다리 게임 ( 16928 )

• 게임은 정육면체 주사위를 사용하며, 주사위의 각 면에는 1부터 6까지 수가 하나씩 적혀있다. 게임은 크기가 10×10이고, 총 100개의 칸으로 나누어져 있는 보드판에서 진행된다
• 보드판에는 1부터 100까지 수가 하나씩 순서대로 적혀져 있다
• 플레이어는 주사위를 굴려 나온 수만큼 이동해야 한다
• 예를 들어, 플레이어가 i번 칸에 있고, 주사위를 굴려 나온 수가 4라면, i+4번 칸으로 이동해야 한다
• 만약 주사위를 굴린 결과가 100번 칸을 넘어간다면 이동할 수 없다
• 도착한 칸이 사다리면, 사다리를 타고 위로 올라간다
• 뱀이 있는 칸에 도착하면, 뱀을 따라서 내려가게 된다
• 즉, 사다리를 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 크고, 뱀을 이용해 이동한 칸의 번호는 원래 있던 칸의 번호보다 작아진다
• 게임의 목표는 1번 칸에서 시작해서 100번 칸에 도착하는 것이다
• 게임판의 상태가 주어졌을 때, 100번 칸에 도착하기 위해 주사위를 굴려야 하는 횟수의 최솟값을 구해보자

#include<bits/stdc++.h>
using namespace std;

const int MAX = 102;

void game(vector<int>& warp, vector<bool>& visited, int location, int c)
{
	queue<pair<int, int>> que;
	que.push(make_pair(location, c));
	visited[location] = true;

	while (!que.empty())
	{
		// 다음 위치 세팅
		int x = que.front().first;
		int cnt = que.front().second;
		que.pop();

		for (int i = 1; i <= 6; i++)
		{
			// 주사위 숫자만큼 이동
			int nx = x + i;
			int ncnt = cnt + 1;

			// 도착 했다면 정답을 출력
			if (nx == 100)
			{
				cout << ncnt << endl;
				return;
			}
			// 이 조건문이 없어도 정상 실행되는것 확인
			else if (nx < 100)
			{
				// 워프를 태울수 있을때 까지 태운다
				while (warp[nx] != 0)
				{
					nx = warp[nx];
				}

				// 아직 방문한적 없는 노드라면 큐에 넣는다
				if (!visited[nx])
				{
					que.push(make_pair(nx, ncnt));
					visited[nx] = true;
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

	vector<int> warp(MAX, 0);
	vector<bool> visited(MAX, false);

	int sadari, snake;
	cin >> sadari >> snake;

	for (int i = 0; i < sadari; i++)
	{
		int from = 0, to = 0;
		cin >> from >> to;
		warp[from] = to;
	}
	for (int i = 0; i < snake; i++)
	{
		int from = 0, to = 0;
		cin >> from >> to;
		warp[from] = to;
	}

	game(warp, visited, 1, 0);

	return 0;
}

04-2 연구소 ( 14502 )

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

#include<bits/stdc++.h>
using namespace std;

int answer = 0;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

// 여기서는 참조자를 사용해도 된다
void BFS(vector<vector<int>>& mymap)
{
	queue<pair<int, int>> que;

	// 바이러스 최초 위치들을 모두 큐에 담는다
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 2)
				que.push({ x, y });
		}
	}

	// 바이러스를 최대한 퍼뜨린다
	while (!que.empty())
	{
		int x = que.front().first;
		int y = que.front().second;
		que.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || mymap[0].size() <= nx || mymap.size() <= ny || mymap[ny][nx] != 0)
				continue;

			que.push({ nx, ny });
			mymap[ny][nx] = 2;
		}
	}

	// 바이러스가 모두 퍼진 상태에서 안전 영역 크기를 계산한다
	int cnt = 0;
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 0)
				cnt++;
		}
	}

	answer = max(answer, cnt);
}

// 여기서는 참조자를 사용하면 안된다
void DFS(vector<vector<int>> mymap, int x, int y, int cnt)
{
	mymap[y][x] = 1;
	cnt = cnt - 1;

	// 벽을 더이상 세울수 없다면 바이러스를 퍼뜨린다
	if (cnt == 0)
	{
		BFS(mymap);

		return;
	}

	// 벽 2개를 세울수 있는 모든 경우의 수를 체크한다
	for (int y = 0; y < mymap.size(); y++)
	{
		for (int x = 0; x < mymap[0].size(); x++)
		{
			if (mymap[y][x] == 0)
				DFS(mymap, x, y, cnt);
		}
	}
}

int main()
{
	int N, M;
	cin >> N >> M;

	vector<vector<int>> mymap(N, vector<int>(M, 0));

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
			cin >> mymap[y][x];
	}

	// 벽 3개를 세울수 있는 모든 경우의 수를 체크한다
	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < M; x++)
		{
			if (mymap[y][x] == 0)
				DFS(mymap, x, y, 3);
		}
	}

	cout << answer << endl;

	return 0;
}

04-3 점프 게임 ( 15558 )

• 각 칸의 정보가 주어졌을 때, 게임을 클리어 할 수 있는지, 없는지 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

typedef struct
{
	int x, y, x_limit;
}node;

int main()
{
	vector<vector<bool>> visited(2, vector<bool>(200001, false));

	int N, K;
	cin >> N >> K;

	for (int y = 0; y < 2; y++)
	{
		for (int x = 0; x < N; x++)
		{
			char value;
			cin >> value;

			if (value == '0')
			{
				visited[y][x] = true;
			}
			else
			{
				visited[y][x] = false;
			}
		}
	}

	// 필요한 변수 초기화
	bool flag = false;
	queue<node> que;
	que.push({ 0, 0, 0 });
	visited[0][0] = true;

	while (!que.empty())
	{
		// 다음 위치 세팅
		node cur = que.front();
		int x = cur.x, y = cur.y, x_limit = cur.x_limit;
		que.pop();

		// 목적지를 넘어서면 플래그를 true로 세팅한다
		if (N <= x)
		{
			flag = true;
			break;
		}

		//전진
		if (visited[y][x + 1] == false)
		{
			visited[y][x + 1] = true;
			que.push({ x + 1, y, x_limit + 1 });
		}

		//후진 
		if (visited[y][x - 1] == false && x_limit < x - 1)
		{
			visited[y][x - 1] = true;
			que.push({ x - 1, y, x_limit + 1 });
		}

		//점프
		if (visited[1 - y][x + K] == false)
		{
			visited[1 - y][x + K] = true;
			que.push({ x + K, 1 - y, x_limit + 1 });
		}

	}

	// 플래그에 따라 결과 출력
	if (flag == false)
		cout << 0;
	else
		cout << 1;
}

04-4 4연산 ( 14395 )

• 정수 s가 주어진다
• 정수 s의 값을 t로 바꾸는 최소 연산 횟수를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

const long long MAX = 1e9;

set<long long> visited;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    int start, target;
    cin >> start >> target;

    if(start == target)
    {
        cout << 0 << "\n";
        return 0;
    }
    
    // 필요한 변수 초기화
    queue<pair<long long, string>> que;
    que.push({start, ""});
    
    while (!que.empty())
    {
        // 다음 숫자 세팅
        long long n = que.front().first;
        string temp = que.front().second;
        que.pop();

        // 원하는 숫자라면 연산자 출력후 리턴
        if (n == target)
        {
            cout << temp << "\n";
            return 0;
        }

        // 현재 노드에서 방문할 수 있는 노드를 모두 큐에 담는다 ( https://twpower.github.io/92-how-to-use-set-in-cpp // count 함수에 대한 정보 )
        if (0 <= n * n && n * n <= MAX && visited.count(n*n) == 0 )
        {
            que.push({ n * n, temp + "*" });
            visited.insert(n*n);
        }
        if (0 <= n + n && n + n <= MAX && visited.count(n+n) == 0)
        {
            que.push({ n + n, temp + "+" });
            visited.insert(n + n);
        }
        if (0 <= n - n && n - n <= MAX && visited.count(n-n) == 0)
        {
            que.push({ n - n, temp + "-" });
            visited.insert(n - n);
        }
        if (n != 0 && 0 <= n / n && n / n <= MAX && visited.count(n/n) == 0)
        {
            que.push({ n / n, temp + "/" });
            visited.insert(n / n);
        }

    }
    
    // 변환이 불가능한 경우 -1을 출력한다
    cout << -1 << "\n";
    return 0;
}

04-5 물통 ( 2251 )

• 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다
• 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다
• 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다
• 이 과정에서 손실되는 물은 없다고 가정한다
• 이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다
• 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오

// https://j2wooooo.tistory.com/130 이분은 push 이후 바로 방문처리 하게함

#include<bits/stdc++.h>
using namespace std;

typedef struct
{
	int a, b, c;
}node;

const int MAX = 201;

int CapacityA, CapacityB, CapacityC;
bool visited[MAX][MAX][MAX];

vector<int> answer;

void Input()
{
	cin >> CapacityA >> CapacityB >> CapacityC;
}

void Solution()
{
	// 필요한 변수 초기화
	queue<node> que;
	que.push({ 0, 0, CapacityC });

	while (!que.empty())
	{
		// 다음 물높이 세팅
		node cur = que.front();
		int a = cur.a;
		int b = cur.b;
		int c = cur.c;
		que.pop();

		// 해당 물높이 방문 처리
		if (visited[a][b][c] == true) continue;
		visited[a][b][c] = true;

		// 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있는 물의 양을 정답지에 넣는다
		if (a == 0) answer.push_back(c);

		// A물통에서 B물통으로 줄 때
		if (CapacityB < a + b) que.push({ a + b - CapacityB, CapacityB, c });
		else que.push({ 0, a + b, c });

		// A물통에서 C물통으로 줄 때
		if (CapacityC < a + c) que.push({ a + c - CapacityC, b, CapacityC });
		else que.push({ 0, b, a + c });

		// B물통에서 A물통으로 줄 때
		if (CapacityA < b + a) que.push({ CapacityA, b + a - CapacityA, c });
		else que.push({ b + a, 0, c });

		// B물통에서 C물통으로 줄 때
		if (CapacityC < b + c) que.push({ a, b + c - CapacityC, CapacityC });
		else que.push({ a, 0, b + c });

		// C물통에서 A물통으로 줄 때
		if (CapacityA < c + a) que.push({ CapacityA, b, c + a - CapacityA });
		else que.push({ c + a, b, 0 });

		// C물통에서 B물통으로 줄 때
		if (CapacityB < c + b) que.push({ a, CapacityB, c + b - CapacityB });
		else que.push({ a, c + b, 0 });
	}

	sort(answer.begin(), answer.end());

	for (int i = 0; i < answer.size(); i++)
	{
		cout << answer[i] << " ";
	}
}

void Solve()
{
	Input();
	Solution();
}

int main(void)
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	Solve();

	return 0;
}

04-6 토마토 ( 7576 )

• 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라

#include <bits/stdc++.h>
using namespace std;

// 그래프 관련 변수
int n, m;
int graph[1001][1001];
queue<pair<int, int>> q;

// 상, 하, 좌, 우 이동
int dx[4] = { -1, 1, 0, 0 };
int dy[4] = { 0, 0, -1, 1 };

void bfs(void)
{
	while (!q.empty())
	{
		// main에서 분명히 y 좌표를 first에 입력해놨다
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || m <= nx || n <= ny) continue;
			if (graph[ny][nx] == -1) continue;

			if (graph[ny][nx] == 0)
			{
				q.push({ ny, nx });
				graph[ny][nx] = graph[y][x] + 1;
			}
		}
	}
}

int main()
{
	// 입력받기
	cin >> m >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			scanf("%d", &graph[i][j]);
			if (graph[i][j] == 1)
			{
				// 분명히 y 좌표를 first에 입력해놨다
				q.push({ i, j });
			}
		}
	}

	// BFS를 통해 탐색
	bfs();

	// 안 익은 토마토 없나 확인
	int result = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			result = max(result, graph[i][j] - 1);

			if (graph[i][j] == 0)
			{
				cout << -1 << endl;
				return 0;
			}
		}
	}

	// 결과 출력
	printf("%d\n", result);
	return 0;
}

04-7 경쟁적 전염 ( 18405 )

• 시험관의 크기와 바이러스의 위치 정보가 주어졌을 때, S초가 지난 후에 (X,Y)에 존재하는 바이러스의 종류를 출력하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

const int MAX = 202;

int arr[MAX][MAX];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

struct Virus
{
	int virus;
	int x;
	int y;
};

bool cmp(const Virus& v1, const Virus& v2)
{
	return v1.virus < v2.virus;
}

int main()
{
	vector<Virus> vec;

	int N, K;
	cin >> N >> K;

	for (int y = 0; y < N; y++)
	{
		for (int x = 0; x < N; x++)
		{
			cin >> arr[y][x];
			vec.push_back({ arr[y][x], x, y });
		}
	}

	int S, X, Y;
	cin >> S >> Y >> X;

	int s = 0;
	sort(vec.begin(), vec.end(), cmp);

	while (s < S)
	{
		int len = vec.size();
		for (int j = 0; j < len; j++)
		{
			Virus v = vec[j];
			for (int i = 0; i < 4; i++)
			{
				int nx = v.x + dx[i];
				int ny = v.y + dy[i];

				if (nx < 0 || ny < 0 || N <= nx || N <= ny) continue;

				if (arr[ny][nx] == 0)
				{
					arr[ny][nx] = v.virus;
					vec.push_back({ arr[ny][nx], nx, ny });
				}
			}
		}

		if (0 < arr[Y - 1][X - 1]) break;
		s++;
	}

	cout << arr[Y - 1][X - 1];

	return 0;
}

04-8 숨바꼭질 4 ( 13913 )

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

#include<bits/stdc++.h>
using namespace std;
#define max 1000001

int N, K;
int parent[max];
bool visited[max];

// 현재 위치와 걸린 시간
struct node
{
	int cur;
	int time;
};

void bfs(int start)
{
	queue<node> q;
	q.push({ start, 0 });
	visited[start] = true;

	while (!q.empty())
	{
		int cur = q.front().cur;
		int time = q.front().time;
		q.pop();

		// 목적지 도착 하면 종료
		if (cur == K)
		{
			cout << time << endl;
			return;
		}

		// 해당 지점을 처음 방문하는 경우 부모 설정 및 방문 처리
		if (0 <= cur - 1)
		{
			if (!visited[cur - 1])
			{
				q.push({ cur - 1, time + 1 });
				visited[cur - 1] = true;
				parent[cur - 1] = cur;
			}
		}
		if (cur + 1 < max)
		{
			if (!visited[cur + 1])
			{
				q.push({ cur + 1, time + 1 });
				visited[cur + 1] = true;
				parent[cur + 1] = cur;
			}
		}
		if (cur * 2 < max)
		{
			if (!visited[cur * 2])
			{
				q.push({ cur * 2, time + 1 });
				visited[cur * 2] = true;
				parent[cur * 2] = cur;
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> N >> K;
	bfs(N);

	stack<int> stk;

	stk.push(K);
	int cur = K;
	while (cur != N)
	{
		stk.push(parent[cur]);
		cur = stk.top();
	}

	while (!stk.empty())
	{
		cout << stk.top() << ' ';
		stk.pop();
	}

	return 0;
}

04-9 이모티콘 ( 14226 )

• 영선이가 S개의 이모티콘을 화면에 만드는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오

// https://junbastick.tistory.com/17 참고
#include<iostream>
#include<vector>
#include<queue>

#define endl "\n"
using namespace std;

#define MAX 1001
bool visit[MAX][MAX];

int BFS(int S)
{
	queue<pair<pair<int, int>, int>> q;
	q.push(make_pair(make_pair(1, 0), 0));
	visit[1][0] = true;

	while (!q.empty())
	{
		int screen = q.front().first.first;
		int clip = q.front().first.second;
		int time = q.front().second;
		q.pop();

		// 각 시간대 별로 현재 상황을 사진 찍어놓는다는 느낌
		if (screen == S)
			return time;
		if (!visit[screen][screen])
		{
			q.push(make_pair(make_pair(screen, screen), time + 1));
			visit[screen][screen] = true;
		}
		if (screen + clip <= S && !visit[screen + clip][clip])
		{
			q.push(make_pair(make_pair(screen + clip, clip), time + 1));
			visit[screen + clip][clip] = true;
		}
		if (2 <= screen - 1 && !visit[screen - 1][clip])
		{
			q.push(make_pair(make_pair(screen - 1, clip), time + 1));
			visit[screen - 1][clip] = true;
		}
	}
}

void Answer()
{
	int S;
	cin >> S;
	cout << BFS(S) << endl;
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	Answer();
	return 0;
}

#include <bits/stdc++.h>
using namespace std;

//1개는 이미 입력
int S;

int visited[3000][3000];
int main()
{
	cin >> S;
	//현재 상태, 클립보드에 저장된 개수

	queue<pair<int, int>> q;
	q.push({ 1,0 });
	visited[1][0] = 1;

	while (!q.empty())
	{
		auto cur = q.front();
		q.pop();
		int now = cur.first;
		int clip = cur.second;

		//체크
		if (now == S)
		{
			cout << visited[now][clip] - 1 << '\n';
			break;
		}

		//1.복사
		int nextClip = now;
		if (visited[now][nextClip] == 0)
		{
			q.push({ now, nextClip });
			visited[now][nextClip] = visited[now][clip] + 1;
		}

		//2.붙여넣기
		if (now + clip <= S)
		{
			if (visited[now + clip][clip] == 0)
			{
				q.push({ now + clip, clip });
				visited[now + clip][clip] = visited[now][clip] + 1;
			}
		}

		//3.삭제
		if (now > 0)
		{
			if (visited[now - 1][clip] == 0)
			{
				q.push({ now - 1, clip });
				visited[now - 1][clip] = visited[now][clip] + 1;
			}
		}
	}

	return 0;
}

04-10 알고스팟 ( 1261 )

• 현재 (1, 1)에 있는 알고스팟 운영진이 (N, M)으로 이동하려면 벽을 최소 몇 개 부수어야 하는지 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

#define MAX 1e9

int N, M;
int board[101][101];
int dist[101][101];
int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };

void bfs()
{
	queue<pair<int, int>> q;
	q.push({ 0,0 });
	dist[0][0] = 0;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;

			if (board[ny][nx] == 0)
			{
				// 이 경우가 성립한다면 벽을 부술 필요가
				// 없는데 부순애가 지나갔다는 의미
				if (dist[y][x] < dist[ny][nx])
				{
					dist[ny][nx] = dist[y][x];
					q.push({ nx,ny });
				}
			}
			else if (board[ny][nx] == 1)
			{
				// 이 경우가 성립하다면 벽을 더 적게
				// 부수고 지나갈수 있다는 의미
				if (dist[y][x] + 1 < dist[ny][nx])
				{
					dist[ny][nx] = dist[y][x] + 1;
					q.push({ nx,ny });
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> M >> N;
	string str;

	for (int i = 0; i < N; i++)
	{
		cin >> str;
		for (int j = 0; j < M; j++)
		{
			dist[i][j] = MAX;
			board[i][j] = str[j] - '0';
		}
	}

	bfs();
	cout << dist[N - 1][M - 1] << "\n";

	return 0;
}

Chapter 05 그래프

05-1 ABCDE ( 13023 )

• 위와 같은 친구 관계가 존재하는지 안하는지 구하는 프로그램을 작성하시오

// 기본 그래프 문제 3개
// 다익스트라 문제 3개, 참고로 다익스트라는 DP의 일종이다
// 플로이드 워셜 문제 3개
// 유니온 파인드 문제 3개

#include<bits/stdc++.h>
using namespace std;

vector<int> people[2000];
bool visited[2000];
bool ispossible;

void dfs(int node, int depth)
{
	if (depth == 4)
	{
		ispossible = true;
		return;
	}

	visited[node] = true;
	for (int i = 0; i < people[node].size(); ++i)
	{
		int next = people[node][i];
		// if(!visited[next] && ispossible == false) 이렇게 하면 좀더 최적화 된다
		if (!visited[next])
			dfs(next, depth + 1);
	}
	visited[node] = false;
}

int N, M;
int main()
{
	cin >> N >> M;
	for (int i = 0; i < M; ++i)
	{
		int a, b;
		cin >> a >> b;
		people[a].push_back(b);
		people[b].push_back(a);
	}

	for (int i = 0; i < N; ++i)
	{
		dfs(i, 0);
		if (ispossible) break;
	}

	cout << ispossible << '\n';
}

05-2 DFS와 BFS ( 1260 )

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

vector<int> vec[1001];
queue<int> Q;
int chDFS[1001], chBFS[1001], N;

void DFS(int v)
{
	cout << v << " ";

	chDFS[v] = 1;
	for (int i = 0; i < vec[v].size(); i++)
	{
		int next = vec[v][i];
		if (!chDFS[next])
		{
			DFS(next);
		}
	}
}
void BFS(int v)
{
	Q.push(v);
	chBFS[v] = 1;

	while (!Q.empty())
	{
		int cur = Q.front();
		Q.pop();

		cout << cur << " ";

		for (int i = 0; i < vec[cur].size(); i++)
		{
			int next = vec[cur][i];
			if (!chBFS[next])
			{
				Q.push(next);
				chBFS[next] = 1;
			}
		}
	}
}
int main()
{
	int M, V, a, b;
	cin >> N >> M >> V;

	while (M--)
	{
		cin >> a >> b;
		vec[a].push_back(b);
		vec[b].push_back(a);
	}

	for (int i = 1; i <= N; i++)
		sort(vec[i].begin(), vec[i].end());

	DFS(V);
	cout << "\n";
	BFS(V);
}

05-3 연결 요소의 개수 ( 11724 )

• 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

vector<int> vect[1001];	//인접리스트
bool visited[1001]; //방문기록
int N, M;

/* DFS : 방문기록 남기는 용도 */
void DFS(int vertex)
{
    visited[vertex] = true;
    for (int i = 0; i < vect[vertex].size(); i++) //최댓값 주의 : 벡터 그 원소에 해당하는 크기만큼 돌아야함
    {
        int idx = vect[vertex][i];
        if (!visited[idx])
        {
            DFS(idx);
        }
    }
}

int main()
{
    int u, v;
    int cnt = 0;
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        cin >> u >> v;
        vect[u].push_back(v);
        vect[v].push_back(u); //무방향 그래프이기 때문
    }

    for (int i = 1; i <= N; i++) //빠짐없이 탐색하기 위해
    {
        if (!visited[i])
        {
            cnt++;
            DFS(i);
        }
    }
    cout << cnt << "\n";
}

05-4 이분 그래프 ( 1707 )

• 그래프가 입력으로 주어졌을 때, 이 그래프가 이분 그래프인지 아닌지 판별하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

#define RED 2
#define BLUE 3

vector<int> vect[20001]; //인접리스트
int visited[20001]; //방문기록
int V, E;

/* DFS 실행 */
void DFS(int start)
{
    //방문안한 점이면 RED
    if (visited[start] == 0)
        visited[start] = RED;

    //연결된 점들 방문
    for (int i = 0; i < vect[start].size(); i++)
    {
        int idx = vect[start][i];
        if (visited[idx] == 0) //방문 안한 점이면
        {
            //요소에 방문기록 남김(색칠하기)
            if (visited[start] == RED)
                visited[idx] = BLUE;
            else if (visited[start] == BLUE)
                visited[idx] = RED;

            //요소별로 방문
            DFS(idx);
        }
    }
}

/* 이분그래프 검사 */
int check()
{
    //인접한 노드와 색이 같으면 이분그래프 X
    for (int i = 1; i <= V; i++)
    {
        //연결된게 자기자신 뿐일 경우엔 size가 0이라서 돌아가지 않는다.
        for (int j = 0; j < vect[i].size(); j++)
        {
            int idx = vect[i][j];
            if (visited[i] == visited[idx]) 
            {
                return false;
            }
        }
    }
    return true;
}

int main()
{
    int T;    //테스트케이스
    int u, v; //노드 담을 변수

    cin >> T;
    while (T--)
    {
        cin >> V >> E;
        for (int i = 0; i < E; i++)
        {
            cin >> u >> v;
            vect[u].push_back(v);
            vect[v].push_back(u);
        }

        
        //빠짐없이 방문하기 위해 1부터 원소 개수까지 다 방문해봄
        for (int i = 1; i <= V; i++)
        {
            if (visited[i] == 0)
                DFS(i);
        }

        if (check() == 0) //이분그래프인지 검사
            cout << "NO\n";
        else
            cout << "YES\n";

        memset(visited, 0, sizeof(visited));
        memset(vect, 0, sizeof(vect));
    }
}

// https://hongjw1938.tistory.com/117 이분 그래프 설명

#include<bits/stdc++.h>
using namespace std;

#define RED 1
#define BLUE 2

vector<int> vect[20001];
int visited[20001];
int V, E;

void BFS(int start)
{
	queue<int> q;
	q.push(start);
	visited[start] = RED;

	while (!q.empty()) //큐가 빌 때 까지 반복(전체)
	{
		int now = q.front();
		q.pop();

		for (int i = 0; i < vect[now].size(); i++)
		{
			int next = vect[now][i];

			if (visited[next] == 0)
			{
				q.push(next);

				if (visited[now] == RED) visited[next] = BLUE;
				else if (visited[now] == BLUE) visited[next] = RED;
			}
		}
	}
}

bool check()
{
	for (int i = 1; i <= V; i++)
	{
		for (int j = 0; j < vect[i].size(); j++)
		{
			int next = vect[i][j];

			if (visited[i] == visited[next])
				return false;
		}
	}

	return true;
}

int main()
{
	int K, u, v;
	cin >> K;

	while (K--)
	{
		cin >> V >> E;
		for (int i = 0; i < E; i++)
		{
			cin >> u >> v;
			vect[u].push_back(v);
			vect[v].push_back(u);
		}

		//빠짐없이 방문하기 위해 노드 개수만큼 BFS 돌려줘야함
		for (int i = 1; i <= V; i++)
		{
			if (visited[i] == 0)
			{
				BFS(i);
			}
		}

		//이분그래프 검사
		if (check())
			cout << "YES\n";
		else
			cout << "NO\n";

		memset(visited, 0, sizeof(visited));
		memset(vect, 0, sizeof(vect));
	}
}

05-5 단지번호붙이기 ( 2667 )

• 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;
#define MAX 26

int n, cnt = 0;
string arr[MAX];
bool visited[MAX][MAX] = { 0 };

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };
queue<pair<int, int>> q;

vector<int> result;

void bfs(int x, int y)
{
	q.push({ x,y });
	visited[y][x] = true;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		cnt++;

		for (int i = 0; i < 4; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || n <= nx || n <= ny) continue;

			if (visited[ny][nx] == false && arr[ny][nx] == '1')
			{
				q.push({ nx,ny });
				visited[ny][nx] = true;
			}
		}
	}
}

int main()
{
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int y = 0; y < n; y++)
	{
		for (int x = 0; x < n; x++)
		{
			if (arr[y][x] == '1' && visited[y][x] == false)
			{
				cnt = 0;
				bfs(x, y);
				result.push_back(cnt);
			}
		}
	}

	sort(result.begin(), result.end());

	cout << result.size() << "\n";
	for (int i = 0; i < result.size(); i++)
	{
		cout << result[i] << "\n";
	}
}

05-6 미로 탐색 ( 2178 )

• 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main()
{
	vector<vector<int>> board(110, vector<int>(110, 0));
	vector<vector<bool>> visited(110, vector<bool>(110, false));

	int N, M;
	cin >> N >> M;

	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			scanf("%1d", &board[i][j]);
		}
	}

	queue<pair<pair<int, int>, int>> que;
	que.push(make_pair(make_pair(0, 0), 1));
	visited[0][0] = true;

	while (!que.empty())
	{
		int x = que.front().first.first;
		int y = que.front().first.second;
		int count = que.front().second;
		que.pop();

		if (x == M - 1 && y == N - 1)
		{
			cout << count << endl;
			return 0;
		}

		for (int i = 0; i < 4; ++i)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;

			if (visited[ny][nx] == false && board[ny][nx] == 1)
			{
				que.push(make_pair(make_pair(nx, ny), count + 1));
				visited[ny][nx] = true;
			}
		}
	}
}

05-7 특정 거리의 도시 찾기 ( 18352 )

• 이 때 특정한 도시 X로부터 출발하여 도달할 수 있는 모든 도시 중에서, 최단 거리가 정확히 K인 모든 도시들의 번호를 출력하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

vector<int> answer;

const int MAX = 300001;

void getCityCount(vector<vector<int>>& graph, vector<bool>& visited, int node, int target_distance)
{
    // 필요한 변수 초기화
    queue<pair<int,int>> que;
    que.push(make_pair(node, 0));
    visited[node] = true;
    
    while(!que.empty())
    {
        // 다음 위치 세팅
        int cur = que.front().first;
        int distance = que.front().second;
        que.pop();
        
        // 원하는 거리의 도시이면 정답지에 넣는다
        if(distance == target_distance) answer.push_back(cur);
        
        // 현재 노드에서 방문할 수 있는 노드를 모두 큐에 담는다
        for(auto next : graph[cur])
        {
            if(visited[next]) continue;
            
            que.push(make_pair(next, distance + 1));
            visited[next] = true;
        }
    }
}

int main()
{
    int N = 0, M = 0, K = 0, X = 0;
    cin >> N >> M >> K >> X;
    
    // https://leeeegun.tistory.com/m/3 참고
    vector<vector<int>> graph(N+1);
    vector<bool> visited(MAX, false);
    
    for(int i = 0; i < M; ++i)
    {
        int from = 0, to = 0;
        cin >> from >> to;
        
        graph[from].push_back(to);
    }
    
    getCityCount(graph, visited, X, K);
    
    if(answer.size() == 0)
    {
        cout << -1 << endl;
    }
    else
    {
        sort(answer.begin(), answer.end());
        
        for(auto value : answer)
        {
            cout << value << endl;
        }   
    }
}

05-8 나이트의 이동 ( 7562 )

• 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

#include <bits/stdc++.h>
using namespace std;

int dx[] = { -2, -2, -1, -1, 1, 1, 2, 2 };
int dy[] = { 1, -1, 2, -2, 2, -2, 1, -1 };

int graph[301][301];
bool visited[301][301];

int bfs(int size, int beginX, int beginY, int endX, int endY)
{
	queue<pair<int, int>> q;
	q.push(make_pair(beginX, beginY));
	visited[beginY][beginX] = true;

	while (!q.empty())
	{
		int x = q.front().first;
		int y = q.front().second;
		q.pop();

		if (x == endX && y == endY) return graph[y][x];

		for (int i = 0; i < 8; i++)
		{
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || ny < 0 || size <= nx || size <= ny) continue;

			// 이전으로 되돌아 갔는데 목적지와 오히려 가까워 질수는 없다는 것을 명심
			if (!visited[ny][nx])
			{
				q.push(make_pair(nx, ny));
				graph[ny][nx] = graph[y][x] + 1;
				visited[ny][nx] = true;
			}
		}
	}
}

int main(void)
{
	int n, m;
	int beginX, beginY;
	int endX, endY;

	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		memset(visited, 0, sizeof(visited));
		memset(graph, 0, sizeof(graph));
		cin >> beginX >> beginY >> endX >> endY;
		cout << bfs(m, beginX, beginY, endX, endY) << endl;
	}
}

05-9 경로 찾기 ( 11403 )

• 가중치 없는 방향 그래프 G가 주어졌을 때, 모든 정점 (i, j)에 대해서, i에서 j로 가는 경로가 있는지 없는지 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

const int MAX = 101;

void floyd(vector<vector<int>>& graph, int N)
{
    for(int k = 0; k < N; ++k)
    {
        for(int x = 0; x < N; ++x)
        {
            for(int nx = 0; nx < N; ++nx)
            {
                // x에서 nx로 가는 길이 없어도 k를 거쳐갈 수 있으면 갈 수 있다고 여긴다
                if(graph[x][k] && graph[k][nx])
                    graph[x][nx] = 1;
            }
        }
    }
}

int main()
{
    vector<vector<int>> graph(MAX, vector<int>(MAX, 0));

    int N;
    cin >> N;
    
    for(int x = 0; x < N; ++x)
    {
        for(int nx = 0; nx < N; ++nx)
        {
            cin >> graph[x][nx];
        }
    }
    
    floyd(graph, N);
    
    for(int x = 0; x < N; ++x)
    {
        for(int nx = 0; nx < N; ++nx)
        {
            cout << graph[x][nx] << " ";
        }
        cout << endl;
    }
}

05-10 Two Dots ( 16929 )

• 게임판의 상태가 주어졌을 때, 사이클이 존재하는지 아닌지 구해보자

#include<bits/stdc++.h>
using namespace std;

int N, M;
char board[51][51];
bool visited[51][51];

const int dy[4] = { 0, 0, 1, -1 };
const int dx[4] = { 1, -1, 0, 0 };

bool search(int row, int col, int brow, int bcol, char alp)
{
	if (visited[row][col]) return true;

	visited[row][col] = true;

	bool ret = false;
	for (int k = 0; k < 4; ++k)
	{
		int ny = row + dy[k];
		int nx = col + dx[k];

		if (!(0 <= ny && ny < N && 0 <= nx && nx < M)) continue;
		if (ny == brow && nx == bcol) continue;
		if (alp != board[ny][nx]) continue;

		ret = ret + search(ny, nx, row, col, alp);
	}

	return ret;
}

int main()
{
	cin >> N >> M;
	for (int row = 0; row < N; ++row)
		for (int col = 0; col < M; ++col)
			cin >> board[row][col];

	for (int row = 0; row < N; ++row)
		for (int col = 0; col < M; ++col)
		{
			if (visited[row][col]) continue;

			if (search(row, col, -1, -1, board[row][col]))
			{
				cout << "Yes" << "\n";
				return 0;
			}
		}

	cout << "No" << "\n";
	return 0;
}

05-11 네트워크 연결 ( 1922 )

• 각 컴퓨터를 연결하는데 필요한 비용이 주어졌을 때 모든 컴퓨터를 연결하는데 필요한 최소비용을 출력하라

// https://velog.io/@y00913/%EB%B0%B1%EC%A4%80-1922-%EB%84%A4%ED%8A%B8%EC%9B%8C%ED%81%AC-%EC%97%B0%EA%B2%B0-C 참고
// https://ongveloper.tistory.com/284 프림 기반
// https://jaimemin.tistory.com/802 우선순위큐 기반

#include<bits/stdc++.h>
using namespace std;

int N, M, res = 0;
int parent[1001];
vector<pair<int, pair<int, int>>> v;

int findParent(int a)
{
	if (parent[a] == a) return a;
	else return parent[a] = findParent(parent[a]);
}

void unionParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);

	if (a != b) parent[b] = a;
}

bool sameParent(int a, int b)
{
	a = findParent(a);
	b = findParent(b);

	if (a == b) return true;
	else return false;
}

void solution()
{
	sort(v.begin(), v.end());

	for (int i = 1; i <= N; i++)
		parent[i] = i;

	for (int i = 0; i < M; i++)
	{
		int a = v[i].second.first;
		int b = v[i].second.second;
		int cost = v[i].first;

		if (!sameParent(a, b))
		{
			unionParent(a, b);
			res += cost;
		}
	}

	cout << res;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	cin >> N;
	cin >> M;

	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;

		v.push_back({ c, {a, b} });
	}

	solution();

	return 0;
}

05-12 여행 가자 ( 1976 )

• 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자

// https://dmsvk01.tistory.com/112 플로이드 워셜
// 아래 풀이법은 Union Find 기법

#include<bits/stdc++.h>
using namespace std;

int N, M;
int root[201];

int find(int node)
{
	if (root[node] == node) return node;
	return root[node] = find(root[node]);
}

void exeunion(int a, int b)
{
	a = find(a);
	b = find(b);

	if (a < b) root[b] = a;
	else root[a] = b;
}

int main()
{
	cin >> N;
	cin >> M;

	for (int i = 1; i <= N; i++) root[i] = i;
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= N; j++)
		{
			int temp;
			cin >> temp;
			if (temp == 1) exeunion(i, j);
		}
	}

	bool is_possible = true;
	int temp;
	cin >> temp;

	int rootnode = find(temp);
	for (int i = 0; i < M - 1; i++)
	{
		int node;
		cin >> node;
		if (rootnode != find(node)) is_possible = false;
	}

	if (is_possible) cout << "YES\n";
	else cout << "NO\n";

	return 0;
}

05-13 게리맨더링 ( 17471 )

• 백준시의 정보가 주어졌을 때, 인구 차이의 최솟값을 구해보자

// https://torbjorn.tistory.com/242 참고

05-14 지름길 (1446)

• 세준이가 운전해야 하는 거리의 최솟값을 출력하시오

// https://velog.io/@minayeah/C-%EB%B0%B1%EC%A4%80-1446-%EC%A7%80%EB%A6%84%EA%B8%B8 참고

#include<bits/stdc++.h>
using namespace std;

const int INF = 10005;
int N, D;

int from, to, cost;

vector<int> m(10005, INF);
vector<pair<int, int>> v[10005];

int main()
{
	cin >> N >> D;

	for (int i = 0; i < N; i++)
	{
		cin >> from >> to >> cost;
		if (to > D || to - from < cost) continue;
		v[to].push_back({ from, cost });
	}


	m[0] = 0;

	for (int i = 1; i <= D; i++)
	{
		m[i] = m[i - 1] + 1;
		for (int j = 0; j < (int)v[i].size(); j++)
		{
			m[i] = min(m[i], m[v[i][j].first] + v[i][j].second);
		}

	}

	cout << m[D];
}

05-15 완전 이진 트리 ( 9934 )

• 상근이가 종이에 적은 순서가 모두 주어졌을 때, 각 레벨에 있는 빌딩의 번호를 구하는 프로그램을 작성하시오

// https://conkjh032.tistory.com/323 참고

05-16 일루미네이션 ( 5547 )

• 상근이네 집의 건물 위치 지도가 주어졌을 때, 조명을 장식할 벽면의 길이의 합을 구하는 프로그램을 작성하시오

// https://yy-03-10.tistory.com/61 참고

#include<bits/stdc++.h>
using namespace std;

int ody[] = { -1,-1,0,0,1,1 };
int odx[] = { 0,1,-1,1,0,1 };

int edy[] = { -1,-1,0,0,1,1 };
int edx[] = { -1,0,1,-1,-1,0 };

int W, H;
int map[102][102];
int chk[102][102];
int answer = 0;
queue<pair<int, int>> inblock;


void Input()
{
	cin >> W >> H;
	for (int i = 0; i < H; i++)
    {
		for (int j = 0; j < W; j++)
        {
			cin >> map[i][j];
		}
	}
}

int Solution(int y, int x)
{
	int sum = 0;
	for (int i = 0; i < 6; i++)
    {
		if (y % 2 == 0)
        {
			int ny = y + ody[i];
			int nx = x + odx[i];

			if (ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx] == 2)
				sum++;
		}
		else
        {
			int ny = y + edy[i];
			int nx = x + edx[i];

			if (ny < 0 || nx < 0 || ny >= H || nx >= W || map[ny][nx] == 2)
				sum++;
		}
	}
    
	return sum;
}

void Outblock(int y, int x)
{
	chk[y][x] = true;
	map[y][x] = 2;
	queue<pair<int, int>> q;
	q.push(make_pair(y, x));

	while (!q.empty())
    {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();

		for (int i = 0; i < 6; i++)
        {
			int ny = (y % 2) ? y + edy[i] : y + ody[i];
			int nx = (y % 2) ? x + edx[i] : x + odx[i];

			if (ny < 0 || ny >= H || nx < 0 || nx >= W)
				continue;

			if (map[ny][nx] == 0 && !chk[ny][nx])
            {
				chk[ny][nx] = true;
				map[ny][nx] = 2;
				q.push(make_pair(ny, nx));
			}
		}
	}
}

int main()
{
	Input();
	for (int i = 0; i < H; i++)
    {
		for (int j = 0; j < W; j++)
        {
			if (map[i][j] == 0 && (i == 0 || i == H - 1 || j == 0 || j == W - 1) && !chk[i][j]) {
				Outblock(i, j);
			}
		}
	}

	for (int i = 0; i < H; i++)
    {
		for (int j = 0; j < W; j++)
        {
			if (map[i][j] == 1)
            {
				answer += Solution(i, j);
			}
		}
	}
    
	cout << answer << "\n";
}

05-17 숫자고르기 ( 2268 )

• 이러한 조건을 만족시키도록 정수들을 뽑되, 최대로 많이 뽑는 방법을 찾는 프로그램을 작성하시오

// https://chosh95.tistory.com/456 참고

Chapter 06 슬라이딩 윈도우, 투 포인터

06-1 귀여운 라이언 ( 15565 )

• 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 크기를 구하여라

#include<bits/stdc++.h>
using namespace std;

int N, K;
vector<int> pos;

int main()
{
	int currentDoll;
	cin >> N >> K;

	for (int i = 0; i < N; ++i)
	{
		cin >> currentDoll;
		if (currentDoll == 1)
			pos.push_back(i);
	}

	if (pos.size() < K)
	{
		cout << -1 << endl;
		return 0;
	}

	int ans = 1e9;
	// size가 5 K가 3이라고 가정하고 상상해 보자
	for (int i = 0; i <= pos.size() - K; ++i)
	{
		ans = min(ans, pos[i + K - 1] - pos[i] + 1);
	}

	cout << ans << endl;
}

06-2 수 고르기 ( 2230 )

• N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

// MAX가 1e9면 안된다는것 주의
#define MAX 2000000000

int main()
{
	int answer = MAX;

	int n = 0, target = 0;
	cin >> n >> target;

	vector<int> vecNumber(n, 0);
	for (int i = 0; i < n; ++i)
		cin >> vecNumber[i];

	sort(vecNumber.begin(), vecNumber.end());

	// target이 0이라면 start가 OutOfBounds를 유발할 수 있다
	int start = 0, end = 0;
	while (start < n && end < n)
	{
		if (vecNumber[end] - vecNumber[start] < target)
			end = end + 1;
		else
		{
			answer = min(answer, vecNumber[end] - vecNumber[start]);
			start = start + 1;
		}
	}

	cout << answer << endl;
}

06-3 겹치는 건 싫어 (20922)

• 이 수열에서 같은 정수를 K개 이하로 포함한 최장 연속 부분 수열의 길이를 구하는 프로그램을 작성해보자

#include<bits/stdc++.h>
#define AMAX 200001
#define DMAX 100001
using namespace std;

int arr[AMAX];
int dup[DMAX];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	for (int i = 1; i <= n; i++)
	{
		cin >> arr[i];
	}

	int answer = 0;
	int left = 1;
	int right = 1;

	while (left <= n && right <= n)
	{
		if (dup[arr[right]] < k)
		{
			dup[arr[right]]++;
			answer = max(answer, right - left + 1);
			right = right + 1;
		}
		else
		{
			dup[arr[left]]--;
			left = left + 1;
		}
	}
	cout << answer;

	return 0;
}

06-4 두 용액 ( 2470 )

• 산성 용액과 알칼리성 용액의 특성값이 주어졌을 때, 이 중 두 개의 서로 다른 용액을 혼합하여 특성값이 0에 가장 가까운 용액을 만들어내는 두 용액을 찾는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n;
	cin >> n;

	vector<int> ans(2);
	int start = 0, end = n - 1, min = 2000000001;
	int arr[n];

	for (int i = 0; i < n; i++) cin >> arr[i];

	sort(arr, arr + n);
	while (start < end)
	{
		int sum = arr[start] + arr[end];

		if (abs(sum) < abs(min))
		{
			ans[0] = arr[start];
			ans[1] = arr[end];
			min = sum;
		}

		if (sum < 0) start++;
		else end--;
	}

	sort(ans.begin(), ans.end());
	for (int i = 0; i < ans.size(); i++) cout << ans[i] << " ";

	return 0;
}

06-5 회전 초밥 ( 2531 )

• 손님이 먹을 수 있는 초밥 가짓수의 최댓값을 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int N, d, k, c;
int dish, cnt, coupon, maxi = 0;
int sushi[300001];
int check[3001];
vector<int> eat;

int main()
{
	// N:접시수 d:초밥종류수 k:연속접시 C:쿠폰번호
	cin >> N >> d >> k >> c;

	// 회전벨트 위 초밥
	for (int i = 0; i < N; i++) cin >> sushi[i];

	// 슬라이딩 윈도우
	for (int i = 0; i < N; i++)
	{
		dish = 0; // 중복된 스시 체크
		coupon = 1; // 쿠폰 스시가 있는지 확인
		for (int j = i; j < i + k; j++)
		{
			if (check[sushi[j % N]] == 1) dish++; // 이미 먹은 초밥일 경우 중복 수 표시	
			else check[sushi[j % N]] = 1; // 처음 먹어보는 초밥일 경우 체크		

			if (sushi[j % N] == c) coupon = 0; // 쿠폰 스시 있을 시
		}

		maxi = max(maxi, k - dish + coupon); //연속으로 먹을 수 있는 최대접시 - 중복접시 + 쿠폰스시	
		memset(check, 0, sizeof(check)); // 체크 초기화
	}

	cout << maxi;
}

06-6 가장 긴 짝수 연속한 부분 수열 (large) ( 22862 )

• 수열 S에서 최대 K번 원소를 삭제한 수열에서 짝수로 이루어져 있는 연속한 부분 수열 중 가장 긴 길이를 구해보자

#include <bits/stdc++.h>
using namespace std;

int seq[1000010];

int main()
{
	ios::sync_with_stdio(0); cin.tie(0);

	int n, k; cin >> n >> k;
	for (int i = 0; i < n; i++) cin >> seq[i];

	int st = 0, en = 0;
	int cnt = (seq[st] & 1) ? 1 : 0;
	int m = 0;

	while (st < n && en < n)
	{
		while (en < n - 1)
		{
			if (seq[en + 1] & 1)
			{
				if (cnt < k)  cnt++;
				else break;
			}
			en++;
		}

		m = max(m, en - st + 1 - cnt);

		if (seq[st] & 1) cnt--;
		st++;
	}

	cout << m;
}

#include <bits/stdc++.h>
using namespace std;

int main()
{
    int result = 0;

    int numCount, maxDeleteCnt;
    cin >> numCount >> maxDeleteCnt;

    vector<int> numbers;
    int input;
    for (int i = 0; i < numCount; i++)
    {
        cin >> input;
        numbers.push_back(input);
    }

    int currentDeleteCnt = 0;
    int currentLen = 0;
    int left = 0;
    int right = 0;

    while (right < numCount)
    {
        if (numbers[right] % 2 == 0)
        {
            currentLen++;
            right++;
            result = max(result, currentLen - currentDeleteCnt);
        }
        else
        {
            if (currentDeleteCnt + 1 <= maxDeleteCnt)
            {
                currentDeleteCnt++;
                currentLen++;
                result = max(result, currentLen - currentDeleteCnt);
                right++;
            }
            else
            {
                if (right > left)
                {
                    if (numbers[left] % 2 == 1) currentDeleteCnt--;
                    left++;
                    currentLen--;
                }
                else
                {
                    left++;
                    right++;
                }
            }
        }
    }

    cout << result;

    return 0;
}

06-7 좋다 ( 1253 )

• N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라

#include<bits/stdc++.h>
using namespace std;

int N;
long long num[2010];
int Left, Right;
int ans;

int main(void)
{
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		cin >> num[i];
	}

	sort(num + 1, num + N + 1);

	for (int i = 1; i <= N; i++)
	{
		long long find = num[i];
		Left = 1;
		Right = N;

		// 투포인터 알고리즘 활용 
		while (Left < Right)
		{
			if (num[Left] + num[Right] == find)
			{
				if (Left == i) Left++;
				else if (Right == i) Right--;
				else
				{
					ans++;
					break;
				}
			}
			else if (num[Left] + num[Right] < find) Left++;
			else Right--;
		}
	}

	cout << ans;

	return 0;
}

06-8 부분합 ( 1806 )

• 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

#define MAX 1e9

int arr[100000];
int main()
{
	int N, S;
	cin >> N >> S;
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	int right = 0;
	int left = 0;
	int sum = arr[0];
	int minlength = MAX;
	while (left < N && right < N)
	{
		// 합이 크면 왼쪽 최소길이 갱신하고 움직이기
		if (S <= sum)
		{
			int length = right - left + 1;
			minlength = min(minlength, length);
			sum = sum - arr[left];
			left++;
		}
		// 합이 작으면 오른쪽 움직이기
		else
		{
			right++;
			sum = sum + arr[right];
		}
	}
    
	// 조건 만족할 수 없으면 0
	if (minlength == MAX)
	{
		minlength = 0;
	}
    
	cout << minlength;
	return 0;
}

06-9 용액 합성하기 ( 14921 )

• 이 중 두 개의 용액을 혼합하여 만들 수 있는 0에 가장 가까운 특성값 B를 출력하시오

#include<bits/stdc++.h>
#define MAX 100000
using namespace std;

int a[MAX];
int answer = 200000000;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];

	int left = 0;
	int right = n - 1;
	sort(a, a + n);
	while (left < right)
	{
		// 두 용액 혼합
		int sum = a[left] + a[right];

		// 0에 더 가까우면 업데이트
		if (abs(sum) < abs(answer))
		{
			answer = sum;
		}

		if (sum == 0)
			break;
		else if (sum < 0)
			left++;
		else
			right--;
	}

	cout << answer;
	return 0;
}

06-10 고냥이 ( 16472 )

• 문자열이 주어졌을 때 이 번역기가 인식할 수 있는 최대 문자열의 길이는 얼마인지가 궁금해졌다

#include<bits/stdc++.h>
using namespace std;
int alpha[26];

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

	int num, len, result = 0;
	string str;
	cin >> num >> str;
	len = str.size();
	int l = 0, r = 0, cnt = 0;

	while (l < len && r < len)
	{
		while (cnt <= num && r < len)
		{
			int idx = str[r++] - 'a';
			alpha[idx]++;
			if (alpha[idx] == 1) cnt++;
			if (cnt <= num) result = max(result, r - l);
		}
		while (num < cnt && l < len)
		{
			int idx = str[l++] - 'a';
			alpha[idx]--;
			if (alpha[idx] == 0) cnt--;
		}
	}

	cout << result;
	return 0;
}

Chapter 07 시뮬레이션

07-1 배열 돌리기 3 ( 16935 )

• 입력으로 주어진 배열에 R개의 연산을 순서대로 수행한 결과를 출력한다

#include<bits/stdc++.h>
using namespace std;

int n, m, r;

void one(vector<vector<int>>& vecArray)
{
	for (int i = 0; i < n / 2; ++i)
		for (int j = 0; j < m; ++j)
			swap(vecArray[i][j], vecArray[n - 1 - i][j]);
}

void two(vector<vector<int>>& vecArray)
{
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m / 2; ++j)
			swap(vecArray[i][j], vecArray[i][m - 1 - j]);
}

void three(vector<vector<int>>& vecArray)
{
	vector<vector<int>> temp(100, vector<int>(100, 0));

	int h = n;

	swap(n, m);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			temp[i][j] = vecArray[h - 1 - j][i];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			vecArray[i][j] = temp[i][j];
}

void four(vector<vector<int>>& vecArray)
{
	vector<vector<int>> temp(100, vector<int>(100, 0));

	int w = m;

	swap(n, m);

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			temp[i][j] = vecArray[j][w - 1 - i];

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			vecArray[i][j] = temp[i][j];
}

void five(vector<vector<int>>& vecArray)
{
	vector<vector<int>> temp(100, vector<int>(100, 0));

	int N = n / 2;
	int M = m / 2;

	// 1 -> 2
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i][j + M] = vecArray[i][j];
		}
	// 2 -> 3
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i + N][j + M] = vecArray[i][j + M];
		}
	// 3 -> 4
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i + N][j] = vecArray[i + N][j + M];
		}
	// 4 -> 1
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i][j] = vecArray[i + N][j];
		}

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			vecArray[i][j] = temp[i][j];

}

void six(vector<vector<int>>& vecArray)
{
	vector<vector<int>> temp(100, vector<int>(100, 0));

	int N = n / 2;
	int M = m / 2;

	//4번을 3번으로
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i + N][j + M] = vecArray[i + N][j];
		}
	// 3번을 2번으로
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i][j + M] = vecArray[i + N][j + M];
		}
	// 2번을 1번으로
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i][j] = vecArray[i][j + M];
		}
	// 1번을 4번으로
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < M; ++j)
		{
			temp[i + N][j] = vecArray[i][j];
		}

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			vecArray[i][j] = temp[i][j];
}

int main()
{
	cin >> n >> m >> r;

	vector<vector<int>> vecArray(100, vector<int>(100, 0));

	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
		{
			cin >> vecArray[i][j];
		}

	for (int i = 0; i < r; ++i)
	{
		int num;
		cin >> num;
		if (num == 1)
			one(vecArray);
		else if (num == 2)
			two(vecArray);
		else if (num == 3)
			three(vecArray);
		else if (num == 4)
			four(vecArray);
		else if (num == 5)
			five(vecArray);
		else if (num == 6)
			six(vecArray);

	}

	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			cout << vecArray[i][j] << " ";

		cout << "\n";
	}

	return 0;
}

07-2 배열 돌리기 1 ( 16926 )

• 배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자

#include <iostream>
using namespace std;

int map[300][300];
int n, m, r;

void rotate()
{
	// 문제 조건에 min(N, M) mod 2 = 0 라는 힌트가 있다는 것을 명심하자
	// 또한 이것은 돌려야 할 사각형 개수이다
	int check = min(n, m) / 2;

	for (int cnt = 0; cnt < check; cnt++)
	{
		int n_max = n - 1 - cnt;
		int m_max = m - 1 - cnt;

		int tmp = map[cnt][cnt];
		// 위쪽 변 : 왼 <- 오
		for (int i = cnt; i < m_max; i++)
		{
			map[cnt][i] = map[cnt][i + 1];
		}
		// 오른쪽 변 : 아래 <- 위
		for (int i = cnt; i < n_max; i++)
		{
			map[i][m_max] = map[i + 1][m_max];
		}
		// 아래쪽 변 : 왼 -> 오
		for (int i = m_max; cnt < i; i--)
		{
			map[n_max][i] = map[n_max][i - 1];
		}
		// 왼쪽 변 : 위 -> 아래
		for (int i = n_max; cnt < i; i--)
		{
			map[i][cnt] = map[i - 1][cnt];
		}

		map[cnt + 1][cnt] = tmp;
	}
}

int main()
{
	cin.tie(0);
	ios::sync_with_stdio(0);

	cin >> n >> m >> r;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < r; i++) rotate();

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
		{
			cout << map[i][j] << ' ';
		}

		cout << '\n';
	}

	return 0;
}

07-3 배열 돌리기 2 ( 16927 )

• 배열과 정수 R이 주어졌을 때, 배열을 R번 회전시킨 결과를 구해보자

// https://conkjh032.tistory.com/278 참고
#include<bits/stdc++.h>
using namespace std;

int n, m, r;

int mat[301][301];

void print()
{
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m; j++)
			cout << mat[i][j] << " ";

		cout << endl;
	}
}

void solution()
{
	// 꼭지점 4개  
	int y1 = 0;
	int x1 = 0;

	int y2 = n - 1;
	int x2 = 0;

	int y3 = n - 1;
	int x3 = m - 1;

	int y4 = 0;
	int x4 = m - 1;

	// 가장 바깥 영역부터 안으로 들어가기  
	while ((y1 < y2) && (x1 < x4))
	{
		// 영역 내에서 의미있게 회전할 횟수 구하기
		// 예를들어 4*4 사이즈의 배열의 0,0이 처음으로
		// 돌아오려면 12번 회전 시키면 된다
		int move = r % ((y2 - y1) * 2 + (x4 - x1) * 2);

		while (move--)
		{
			// 회전 시키기 
			int tmp = mat[y1][x1];

			// 왼쪽으로
			for (int j = x1; j < x4; j++)
				mat[y1][j] = mat[y1][j + 1];
			// 위로
			for (int i = y4; i < y3; i++)
				mat[i][x4] = mat[i + 1][x4];
			// 오른쪽으로
			for (int j = x3; x2 < j; j--)
				mat[y3][j] = mat[y3][j - 1];
			// 아래로
			for (int i = y2; y1 < i; i--)
				mat[i][x2] = mat[i - 1][x2];

			mat[y1 + 1][x1] = tmp;
		}

		// 회전이 끝났으면, 영역 옮기기  
		y1 += 1;
		x1 += 1;

		y2 -= 1;
		x2 += 1;

		y3 -= 1;
		x3 -= 1;

		y4 += 1;
		x4 -= 1;
	}

	print();
}


int main(void)
{
	cin >> n >> m >> r;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			cin >> mat[i][j];

	solution();
}

07-4 주사위 굴리기 ( 14499 )

• 주사위를 놓은 곳의 좌표와 이동시키는 명령이 주어졌을 때, 주사위가 이동했을 때 마다 상단에 쓰여 있는 값을 구하는 프로그램을 작성하시오

https://excited-hyun.tistory.com/215 참고

#include<bits/stdc++.h>
using namespace std;

int mymap[20][20];
int X[5] = { 0, 1, -1, 0, 0 };
int Y[5] = { 0, 0, 0, -1, 1 };
vector<int> dice(6, 0);

int main()
{
	int n, m, x, y, k;

	scanf("%d %d %d %d %d", &n, &m, &y, &x, &k);
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
			scanf("%d", &mymap[i][j]);
	}

	int move;
	for (int i = 0; i < k; ++i)
	{
		scanf("%d", &move);
		int newX = x + X[move];
		int newY = y + Y[move];

		if (newX < 0 || m <= newX || newY < 0 || n <= newY)
			continue;

		if (move == 1)
			dice = { dice[3], dice[1], dice[0], dice[5], dice[4], dice[2] };
		else if (move == 2)
			dice = { dice[2], dice[1], dice[5], dice[0], dice[4], dice[3] };
		else if (move == 3)
			dice = { dice[4], dice[0], dice[2], dice[3], dice[5], dice[1] };
		else if (move == 4)
			dice = { dice[1], dice[5], dice[2], dice[3], dice[0], dice[4] };

		if (mymap[newY][newX] == 0)
			mymap[newY][newX] = dice[5];
		else
		{
			dice[5] = mymap[newY][newX];
			mymap[newY][newX] = 0;
		}

		cout << dice[0] << endl;

		x = newX;
		y = newY;
	}

	return 0;
}

07-5 톱니바퀴 (2) ( 15662 )

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

// https://intaehwang.tistory.com/108 참고

#include<bits/stdc++.h>
using namespace std;

int gear[1001][8];
int check[1001];
 
int main()
{
    int t;
    cin >> t;
 
    for (int i = 1; i <= t; i++)
    {
        for (int j = 0; j < 8; j++)
            scanf("%1d", &gear[i][j]);
    }
 
    int k;
    cin >> k;
    for (int i = 0; i < k; i++)
    {
        memset(check, 0, sizeof(check));
        int x, y;
        cin >> x >> y;
        check[x] = y;
        
        for (int j = x; j < t; j++)
        {
            if (gear[j][2] != gear[j+1][6]) check[j+1] = -check[j];
            else break;
        }
        for (int j = x; 1 < j; j--)
        {
            if (gear[j-1][2] != gear[j][6]) check[j-1] = -check[j];
            else break;
        }
        for (int j = 1; j <= t; j++)
        {
            if (check[j] == 0) continue;
            else if (check[j] == 1)
            {
                int tmp = gear[j][7];
                for(int cur = 7; 0 < cur; --cur) gear[j][cur] = gear[j][cur-1];
                gear[j][0] = tmp;
            }
            else if (check[j] == -1)
            {
                int tmp = gear[j][0];
                for(int cur = 0; cur < 7; ++cur) gear[j][cur] = gear[j][cur+1];
                gear[j][7] = tmp;
            }
        }
    }
    
    int ans = 0;
    for (int i = 1; i <= t; i++)
        if (gear[i][0] == 1) ans += 1;
    
    cout << ans << endl;
}

07-6 로봇 청소기 ( 14503 )

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

// https://blog.naver.com/PostView.naver?blogId=fbfbf1&logNo=222472445249&categoryNo=34&parentCategoryNo=37&viewDate=&currentPage=1&postListTopCurrentPage=1&from=postView 참고

#include<bits/stdc++.h>
using namespace std;

int board[52][52];
bool check[52][52];

int dy[4] = { -1, 0, 1, 0 };
int dx[4] = { 0, 1, 0, -1 };
int sum = 0;

int main()
{
	ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
	int N, M, r, c, d;
	cin >> N >> M >> r >> c >> d;
	for (int i = 0; i < N; ++i)
	{
		for (int j = 0; j < M; ++j)
		{
			cin >> board[i][j];
		}
	}

	while (true)
	{
		if (check[r][c] == false)
		{
			check[r][c] = true;
			sum++;
		}

		bool ch = false;
		for (int i = 0; i < 4; ++i)
		{
			d = (d + 3) % 4;
			int nx = c + dx[d];
			int ny = r + dy[d];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) continue;

			if (board[ny][nx] == 0 && check[ny][nx] == false)
			{
				c = nx;
				r = ny;
				ch = true;
				break;
			}
		}
		if (!ch)
		{
			int back = (d + 2) % 4;
			int nx = c + dx[back];
			int ny = r + dy[back];

			if (nx < 0 || ny < 0 || M <= nx || N <= ny) break;
			if (board[ny][nx] == 1) break;

			c = nx;
			r = ny;
		}
	}

	cout << sum << "\n";
}

07-7 드래곤 커브 ( 15685 )

• 크기가 100×100인 격자 위에 드래곤 커브가 N개 있다. 이때, 크기가 1×1인 정사각형의 네 꼭짓점이 모두 드래곤 커브의 일부인 정사각형의 개수를 구하는 프로그램을 작성하시오

// https://velog.io/@sj-lee33/%EB%B0%B1%EC%A4%80-15685-%EB%93%9C%EB%9E%98%EA%B3%A4-%EC%BB%A4%EB%B8%8C-c-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%92%80%EC%9D%B4 참고

#include<bits/stdc++.h>
using namespace std;
#define MAX 101

int N;
int x, y, d, g, cnt;
int mymap[MAX][MAX];
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, -1, 0, 1 };
vector<int> direction;

void Make_Dragon_Curve()
{
    int size = direction.size();
    for (int i = size - 1; 0 <= i; i--)
    {
        int temp = (direction.at(i) + 1) % 4;
        x += dx[temp];
        y += dy[temp];
        mymap[y][x] = 1;
        direction.push_back(temp);
    }
}

void Count_Square()
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            if (mymap[i][j] == 1 && mymap[i][j + 1] == 1 && mymap[i + 1][j + 1] && mymap[i + 1][j] == 1)
                cnt++;
        }
    }
}

void Solution()
{
    cin >> N;

    while (N--)
    {
        direction.clear();
        cin >> x >> y >> d >> g;

        // initialize
        mymap[y][x] = 1;

        // generation 0
        x += dx[d];
        y += dy[d];
        mymap[y][x] = 1;
        direction.push_back(d);

        // next 'g' generations
        while (g--)
        {
            Make_Dragon_Curve();
        }
    }

    Count_Square();
    cout << cnt << endl;
}

int main()
{
    Solution();
}

#include<bits/stdc++.h>
using namespace std;

const int MAX = 100 + 1;

bool visited[MAX][MAX];
vector<pair<int, int>> moveDir = { {1, 0}, {0, -1}, {-1, 0}, {0, 1} };

int main(void)
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int y, x, d, g;
		cin >> x >> y >> d >> g;

		vector<int> curve;
		curve.push_back(d);

		for (int j = 0; j < g; j++)
		{
			vector<int> temp = curve;
			for (int k = temp.size() - 1; 0 <= k; k--)
				curve.push_back((temp[k] + 1) % 4);
		}

		visited[y][x] = true;
		for (int j = 0; j < curve.size(); j++)
		{
			x += moveDir[curve[j]].first;
			y += moveDir[curve[j]].second;

			if (0 <= x && x < MAX && 0 <= y && y < MAX)
				visited[y][x] = true;
		}
	}

	int result = 0;
	for (int j = 0; j < MAX - 1; j++)
		for (int k = 0; k < MAX - 1; k++)
			if (visited[j][k] && visited[j][k + 1] && visited[j + 1][k] && visited[j + 1][k + 1])
				result++;

	cout << result << "\n";
	return 0;
}

07-8 LCD Test ( 2290 )

• 지민이의 친한 친구인 지환이는 지민이의 새로운 모니터를 위해 테스트 할 수 있는 프로그램을 만들기로 하였다

// https://luvery93.github.io/articles/2018-11/boj-2290 참고

#include<bits/stdc++.h>
using namespace std;

int view[11][5][3] =
{
{ {0,1,0}, {1,0,1}, {0,0,0}, {1,0,1}, {0,1,0} },
{ {0,0,0}, {0,0,1}, {0,0,0}, {0,0,1}, {0,0,0} },
{ {0,1,0}, {0,0,1}, {0,1,0}, {1,0,0}, {0,1,0} },
{ {0,1,0}, {0,0,1}, {0,1,0}, {0,0,1}, {0,1,0} },
{ {0,0,0}, {1,0,1}, {0,1,0}, {0,0,1}, {0,0,0} },
{ {0,1,0}, {1,0,0}, {0,1,0}, {0,0,1}, {0,1,0} },
{ {0,1,0}, {1,0,0}, {0,1,0}, {1,0,1}, {0,1,0} },
{ {0,1,0}, {0,0,1}, {0,0,0}, {0,0,1}, {0,0,0} },
{ {0,1,0}, {1,0,1}, {0,1,0}, {1,0,1}, {0,1,0} },
{ {0,1,0}, {1,0,1}, {0,1,0}, {0,0,1}, {0,1,0} },
};

int main()
{
	ios::sync_with_stdio(false);
	int s;
	string digit;
	cin >> s >> digit;

	for (int r = 0; r < 5; r++)
	{
		if (r % 2 == 0)
		{
			for (int i = 0; i < digit.size(); i++)
			{
				int d = digit[i] - '0';
				cout << ' ';
				for (int j = 0; j < s; j++)
				{
					cout << (view[d][r][1] == 1 ? '-' : ' ');
				}
				cout << ' ';
				cout << (i == digit.size() - 1 ? '\n' : ' ');
			}
		}
		else
		{
			for (int k = 0; k < s; k++)
			{
				for (int i = 0; i < digit.size(); i++)
				{
					int d = digit[i] - '0';
					cout << (view[d][r][0] == 1 ? '|' : ' ');
					for (int j = 0; j < s; j++)
					{
						cout << ' ';
					}
					cout << (view[d][r][2] == 1 ? '|' : ' ');
					cout << ' ';
				}
				cout << '\n';
			}
		}
	}

	return 0;
}

07-9 겉넓이 구하기 ( 16931 )

• 이 도형의 겉넓이를 구하는 프로그램을 작성하시오

#include<bits/stdc++.h>
using namespace std;

int n, m, board[102][102];
int dx[4] = { 1, -1, 0, 0 };
int dy[4] = { 0, 0, 1, -1 };

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> board[i][j];
		}
	}

	int res = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			for (int d = 0; d < 4; d++)
			{
				int ty = i + dy[d];
				int tx = j + dx[d];

				int gap = board[i][j] - board[ty][tx];
				if (gap > 0)
				{
					res += gap;
				}
			}
		}
	}

	res += 2 * n * m;

	cout << res << '\n';

	return 0;
}

07-10 배열 복원하기 ( 16967 )

• 배열 B와 정수 X, Y가 주어졌을 때, 배열 A를 구해보자

#include<bits/stdc++.h>
using namespace std;

int H, W, X, Y;
int B[601][601];

void input_B()
{
	for (int i = 0; i < H + Y; i++)
	{
		for (int j = 0; j < W + X; j++)
		{
			cin >> B[i][j];
		}
	}
}

void recover_A()
{
	for (int i = Y; i < H; i++)
	{
		for (int j = X; j < W; j++)
		{
			B[i][j] = B[i][j] - B[i - Y][j - X];
		}
	}
}

void print_A()
{
	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			cout << B[i][j] << " ";
		}
		cout << "\n";
	}
}

int main()
{
	cin >> H >> W >> Y >> X;

	input_B();
	recover_A();
	print_A();

	return 0;
}

07-11 컨베이어 벨트 위의 로봇 ( 20055 )

• 몇 번째 단계가 진행 중일때 종료되었는지 출력한다

#include<bits/stdc++.h>
using namespace std;

int main()
{
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);

	int N, K;
	cin >> N >> K;

	vector<int> A(2 * N);
	vector<bool> occupied(2 * N, false);
	for (auto& item : A)
		cin >> item;

	int counter = 0;
	while (true)
	{
		++counter;

		// 1.
		rotate(occupied.rbegin(), occupied.rbegin() + 1, occupied.rend());
		rotate(A.rbegin(), A.rbegin() + 1, A.rend());
		occupied[N - 1] = false;

		// 2.
		for (int i = N - 1; 0 < i; --i)
		{
			if (occupied[i-1] && A[i] && !occupied[i])
			{
				swap(occupied[i-1], occupied[i]);
				--A[i];
			}
		}
		occupied[N - 1] = false;

		// 3.
		if (A[0])
		{
			occupied[0] = true;
			--A[0];
		}

		// 4.
		if (K <= count_if(A.begin(), A.end(), [](int item) { return item == 0; }))
		{
			break;
		}
	}

	cout << counter;

	return 0;
}

Chapter 08 이분 탐색

08-1 기타 레슨 ( 2343 )

• 가능한 블루레이의 크기 중 최소를 구하는 프로그램을 작성하시오

08-2 공유기 설치 (2110)

• 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오

08-3 색종이와 가위 ( 20444 )

• 궁금하지만 화가 나서 코딩에 집중할 수 없는 준성이 대신 코드를 작성해주도록 하자

08-4 징검다리 건너기 (large) ( 22871 )

• 가장 왼쪽 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너갈 수 있는 모든 경우 중 K의 최솟값을 구해보자

08-5 휴게소 세우기 ( 1477 )

• 다솜이는 지금 휴게소를 M개 더 세우려고 한다

08-6 나무 자르기 ( 2805 )

• 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오

08-7 랜선 자르기 ( 1654 )

• 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오

08-8 암벽 등반 ( 2412 )

• 현재 당신이 있는 위치는 (0, 0)이다. 이 위치에서 시작하여 이동 회수를 최소로 하면서 정상에 오르려고 한다

08-9 과자 나눠주기 ( 6236 )

• 현우가 필요한 최소 금액 K를 계산하는 프로그램을 작성하시오

08-10 드래곤 앤 던전 ( 16434 )

• 용사는 수련을 하면 최대 생명력 MaxHP를 늘릴 수 있는데 얼마나 수련해야 할지 고민입니다

맨 위로 이동하기