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

#include <bits/stdc++.h>

using namespace std;

int N, K;
int chessBoard[13][13];
int horseOnChessBoard[13][13][13];
int horseInfo[11][3];  //x, y, dir
int dx[4] = {0, 0, -1, 1};
int dy[4] = {1, -1, 0, 0};
int cnt = 1;
int ans = -1;

void Input();

vector<int> getHorseToMove(int horseX, int horseY, int i) {
    vector<int> horseToMove;
    int idx = -1;

    for (int j = 0; j < K; j++) {
        if (horseOnChessBoard[horseX][horseY][j] == i) {
            idx = j;
            break;
        }
    }

    for (int j = idx; j < K; j++) {
        if (horseOnChessBoard[horseX][horseY][j] == 0) break;
        horseToMove.push_back(horseOnChessBoard[horseX][horseY][j]);
        horseOnChessBoard[horseX][horseY][j] = 0;
    }

    return horseToMove;
}


void turnDirection(int cur, int &horseDir) {
    if (horseDir == 0) horseDir = 1;
    else if (horseDir == 1) horseDir = 0;
    else if (horseDir == 2) horseDir = 3;
    else if (horseDir == 3) horseDir = 2;
    horseInfo[cur][2] = horseDir;
}


bool checkMove(const vector<int> &horseToMove, int nx, int ny, int top) {
    for (int k = 0; k < horseToMove.size(); k++) {
        int curHorse = horseToMove[k];
        horseOnChessBoard[nx][ny][top++] = curHorse;
        horseInfo[curHorse][0] = nx;
        horseInfo[curHorse][1] = ny;
    }

    if(top>=4){
        ans = cnt;
        return true;
    }
    return false;
}


int getTop(int nx, int ny) {
    int top = 0;
    while (horseOnChessBoard[nx][ny][top] != 0) {
        top++;
    }
    return top;
}

bool moveHorse() {
    for (int i = 1; i <= K; i++) {
        int horseX = horseInfo[i][0];
        int horseY = horseInfo[i][1];
        int horseDir = horseInfo[i][2];
        int nx = horseX + dx[horseDir];
        int ny = horseY + dy[horseDir];

        //move or not move check
        if (nx <= 0 || nx > N || ny <= 0 || ny > N || chessBoard[nx][ny] == 2) {
            turnDirection(i, horseDir);
            nx = horseX + dx[horseDir];
            ny = horseY + dy[horseDir];
            if (nx <= 0 || nx > N || ny <= 0 || ny > N || chessBoard[nx][ny] == 2) continue;
        }
        
        //move
        vector<int> horseToMove = getHorseToMove(horseX, horseY, i);
        if (chessBoard[nx][ny] == 1) reverse(horseToMove.begin(), horseToMove.end());
        int top = getTop(nx, ny);

        if (checkMove(horseToMove, nx, ny, top)) {
            return false;
        }
    }

    return true;
}


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

    Input();

    while (moveHorse()) {
        cnt++;

        if (cnt > 1000) {
            cout << -1 << '\n';
            return 0;
        }
    }

    cout << ans << '\n';

    return 0;
}


void Input() {
    cin >> N >> K;

    for (int i = 1; i <= N; i++)
        for (int j = 1; j <= N; j++)
            cin >> chessBoard[i][j];

    for (int i = 1; i <= K; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        horseInfo[i][0] = a;
        horseInfo[i][1] = b;
        horseInfo[i][2] = c - 1;
        horseOnChessBoard[a][b][0] = i;
    }
}

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

1. 문제설명

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;


int N, population[21][21], group[21][21]; //인구수
int ans = INT_MAX;
int x, y, d1, d2;


void Input();

int getMinDifference();

void groupMarking() {
    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (r < x + d1 && c <= y) group[r][c] = 1;
            else if (r <= x + d2 && c > y && c <= N) group[r][c] = 2;
            else if (r >= x + d1 && r <= N && c >= 1 && c < y - d1 + d2) group[r][c] = 3;
            else if (x + d2 < r && y - d1 + d2 <= c) group[r][c] = 4;
        }
    }


    for (int r = 1; r <= N; r++) {
        for (int c = 1; c <= N; c++) {
            if (r + c >= x + y && r + c <= x + y + 2 * d2 && r >= c + x - y && r <= c + x - y + 2 * d1) group[r][c] = 5;
        }
    }

}

//x,y, d1, d2 결정
void divideGroup() {
    for (x = 1; x <= N; x++) {
        for (y = 1; y <= N; y++) {
            for (d1 = 1; d1 <= N; d1++) {
                for (d2 = 1; d2 <= N; d2++) {
                    if (x + d1 + d2 <= N && y - d1 >= 1 && y + d2 > y && y + d2 <= N) {
                        groupMarking();
                        ans = min(ans, getMinDifference());
                    }
                }
            }
        }
    }
}

//인구 차이 최소 구함
int getMinDifference() {
    int groupPopulation[6] = {0};

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            groupPopulation[group[i][j]] += population[i][j];
        }
    }

    int populMax = 0, populMin = INT_MAX;


    for (int i = 1; i <= 5; i++) {
        if (groupPopulation[i] == 0) return INT_MAX;
        populMax = max(populMax, groupPopulation[i]);
        populMin = min(populMin, groupPopulation[i]);
    }

    return populMax - populMin;
};


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

    Input();
    divideGroup();

    if (ans == INT_MAX) cout << -1 << '\n';
    else cout << ans << '\n';


    return 0;
}


void Input() {
    cin >> N;

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

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

1.문제설명

2.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> pii;


int N, population[11]; //인구수
vector<int> adj[11];
bool group[11]; //group 표시

int ans = INT_MAX;


int calDifference() {
    int firstGroupPeople = 0, secondGroupPeople = 0;

    for (int i = 1; i <= N; i++) {
        if (group[i]) {
            firstGroupPeople += population[i];
        } else {
            secondGroupPeople += population[i];
        }
    }

    return abs(firstGroupPeople - secondGroupPeople);
}


bool executeBFS(int startNode) {
    queue<int> Q;
    bool ch[11] = {0};

    Q.push(startNode);
    ch[startNode] = 1;
    while (!Q.empty()) {
        int cur = Q.front();
        Q.pop();
        for (auto nx: adj[cur]) {
            if (!ch[nx] && group[cur]==group[nx]) {
                ch[nx] = 1;
                Q.push(nx);
            }
        }
    }


    for (int i = 1; i <= N; i++) {
        if ((group[i] == group[startNode]) && (ch[i] != 1)) {
            return false;
        }
    }

    return true;
}


bool BFS() {
    //각 그룹 시작점 설정
    int groupOneNode = -1, groupTwoNode = -1;
    for (int i = 1; i <= N; i++) {
        if (groupOneNode != -1 && groupTwoNode != -1) break;
        else if (group[i] == 0) groupOneNode = i;
        else groupTwoNode = i;
    }

    if(groupOneNode ==-1 || groupTwoNode == -1) return false;

    if (executeBFS(groupOneNode) && executeBFS(groupTwoNode)) return true;
    else return false;
}


void bruteForce(int L) {
    if (L == N + 1) {
        if (BFS()) {
            ans = min(ans, calDifference());
        }
        return;
    } else {
        group[L] = 0;
        bruteForce(L + 1);
        group[L] = 1;
        bruteForce(L + 1);
    }
}

void Input();

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

    Input();
    bruteForce(1);

    if (ans == INT_MAX) cout << -1 << '\n';
    else cout << ans << '\n';

    return 0;
}


void Input() {
    cin >> N;

    for (int i = 1; i <= N; i++)
        cin >> population[i];

    for (int i = 1; i <= N; i++) {
        int adjacentNumbers;
        cin >> adjacentNumbers;

        for (int j = 0; j < adjacentNumbers; j++) {
            int num;
            cin >> num;
            adj[i].push_back(num);
        }
    }
}

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

1.문제설명

드래곤 커브가 움직이는 방향을 기준을 바탕으로

드래곤 커브 규칙에 따라 지나는 지점을 표시한 후

사각형을 검사하면서 네 꼭짓점이 모두 지나간 점인지 확인해서 풀 수 있다.

2.문제풀이코드 C++

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


int N;
bool point[103][103];

//방향벡터 모음
// 0 -> 90도회전: 1
// 0 1 -> 90도회전 : 1 2
// 0 1 2 1 -> 90도 회전 : 1 2 3 2
// 0 1 2 1 2 3 2 1
vector<int> getDirectionVector(int d, int g){
    vector<int> direction;
    direction.push_back(d);

    //90도 회전하고 역순으로 추가 g번반복
    for(int i=0; i<g; i++){
        vector<int> newDirection;

        for(int j=0; j<direction.size(); j++){
            newDirection.push_back((direction[j]+1)%4);
        }

        for(int j=direction.size()-1; j>=0; j--){
            direction.push_back(newDirection[j]);
        }
    }

    return direction;
}

void dotPoint(int x, int y, const vector<int>& direction){
    int curX = x, curY = y;

    point[curX][curY] = 1;

    for(int i=0; i<direction.size();i++){
        if(direction[i]==0){
            curY += 1;
        }
        else if(direction[i]==1){
            curX -= 1;
        }
        else if(direction[i]==2){
            curY -= 1;
        }
        else if(direction[i]==3){
            curX += 1;
        }

        point[curX][curY] = 1;
    }
}

int countRectangle(){
    int ans = 0;
    for(int i=0; i<=99; i++){
        for(int j=0; j<=99; j++){
            if(point[i][j] && point[i+1][j] && point[i][j+1] && point[i+1][j+1]){
                ans++;
            }
        }
    }
    return ans;
}



void dragonCurve(int x, int y, int d, int g){
    vector<int> direction = getDirectionVector(d,g);
    dotPoint(x,y, direction);
}

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

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

    cout << countRectangle() << '\n';

    return 0;
}

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

1. 문제설명

1. 용사의 공격력 HATK만큼 몬스터의 생명력을 깎습니다.
2. 몬스터의 생명력이 0 이하이면 전투가 종료되고 용사는 다음 방으로 이동합니다.
3. 몬스터의 공격력만큼 용사의 생명력 HCurHP를 깎습니다.
4. 용사의 생명력이 0 이하이면 전투가 종료되고 용사는 사망합니다.
5. 다시 1부터 진행합니다.

이 순서를 잘 고려하여 몬스터와 용사의 싸움을 잘 구현해야 문제를 해결 할 수 있다.

몬스터가 먼저 죽으면 몬스터는 용사에게 공격할 수 없다!

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


int N, H_atk;
int room[123457][3];

void Input() {
    cin >> N >> H_atk;

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

bool play(ll hp, int attack) {
    ll curHp = hp;
    ll curAttack = attack;

    for (int i = 0; i < N; i++) {
        if (room[i][0] == 1) {
            
            ll turnToMonsterDie = (room[i][2] / curAttack) + (room[i][2] % curAttack > 0 ? 1 : 0);
            ll turnToKnightDie = (curHp / room[i][1]) + (curHp % room[i][1] > 0 ? 1 : 0);

            if (turnToMonsterDie > turnToKnightDie) {
                return false;
            } else {
                curHp -= room[i][1] * (turnToMonsterDie -1);
            }

        } else {
            curHp += room[i][2];
            if (curHp > hp) curHp = hp;

            curAttack += room[i][1];
        }
    }

    return true;
}


ll binarySearch() {
    ll st = 1, en = 9e18;

    while (st <= en) {
        ll mid = st + (en - st) / 2;

        if (play(mid, H_atk)) {
            en = mid - 1;
        } else {
            st = mid + 1;
        }
    }

    return st;
}


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

    Input();
    cout << binarySearch() << '\n';

    return 0;
}

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

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


int N, M;
vector<int> cost;


void Input(){
    cin >> N >> M;

    for(int i=0; i<N; i++){
        int c;
        cin >> c;
        cost.push_back(c);
    }

}

bool withDraw(ll k){
    int cnt = 0;

    ll curMoney = 0;

    for(int i=0; i<N; i++){
        if(k < cost[i]){
            return false;
        }


        if(curMoney < cost[i]) {
            curMoney = k;
            cnt++;
        }

        curMoney -=cost[i];
    }

    return cnt <= M;
}


ll binarySearch(){
    ll st = 1, en = 100000*10000;

    while(st<=en){
        ll mid = (st+en)/2;

        if(withDraw(mid)){
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }
    return st;
}



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

    Input();
    cout << binarySearch() << '\n';

    return 0;
}

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

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


int N, M;
vector<int> lecture;

bool canMakeBlueray(ll lim){
    int cnt = 0;
    int sum = 0;

    for(int i=0; i<N; i++){
        sum += lecture[i];

        if(sum == lim){
            sum = 0;
            cnt++;
        }
        else if(sum > lim){
            sum = lecture[i];
            cnt++;
        }
    }

    if(sum>0) cnt++;
    return cnt <= M;
}

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

    cin >> N >> M;

    int maxNum = 0;
    for(int i=0; i<N; i++){
        int num;
        cin >> num;
        lecture.push_back(num);
        maxNum = max(maxNum, num);
    }


    //각 강의는 10000분을 넘지 않기 때문
    //100000 * 10000 -> long long
    ll st = 1, en = N*10000;


    while(st<=en){
        ll mid = (st+en)/2;

        if(mid >= maxNum && canMakeBlueray(mid)){
            en = mid - 1;
        }
        else{
            st = mid + 1;
        }
    }

    cout << st <<'\n';
    
    return 0;
}

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

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


int n, m;
int startIsland, endIsland;

vector<pair<int, int> > adj[10001];

bool BFS(int st, int en, int weight){
    bool vis[10001];
    memset(vis, 0, sizeof(vis));
    queue<int> Q;

    Q.push(st); vis[st] = 1;
    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(cur == en){
            return true;
        }

        for(auto nx : adj[cur]){
            if(!vis[nx.first]&&nx.second >= weight){
                vis[nx.first] = 1; Q.push(nx.first);
            }
        }
    }
    return false;
}



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

    cin >> n >> m;

    for(int i=0; i<m; i++){
        int a,b,c;
        cin >> a >> b >> c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }

    cin >> startIsland >> endIsland;


    //이분탐색
    int st = 1, en = 1000000000;

    while(st <= en){
        int mid = (st+en)/2;
        if(BFS(startIsland, endIsland, mid)){
            st = mid+1;
        }
        else{
            en = mid-1;
        }
    }

    cout << en << '\n';

    return 0;
}