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;
}

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

1.문제설명

이 문제에서는 덧셈을 할 때 숫자가 중복되면 안되므로

마지막으로 끝난 숫자가 중요하다.

즉 합의 상태를 저장하면서 동시에 마지막 숫자의 상태를 저장해줄 필요가 있다.

이를 점화식으로 나타내면

dp[합][마지막 숫자] = 합을 나타낼 수 있는 경우의 수

로 나타낼 수 있고

더해지는 숫자는 1, 2, 3이기 때문에

dp[i][3] = (dp[i-3][1] + dp[i-3][2]);
dp[i][2] = (dp[i-2][1] + dp[i-2][3]);
dp[i][1] = (dp[i-1][2] + dp[i-1][3]);

이렇게 나타낼 수 있다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;
const int mod = 1000000009;

long long dp[100001][4];

void calDP(){
    dp[1][1] = 1, dp[1][2] = 0, dp[1][3] = 0;
    dp[2][1] = 0, dp[2][2] = 1, dp[2][3] = 0;
    dp[3][1] = 1, dp[3][2] = 1, dp[3][3] = 1;

    for(int i=4; i<=100000; i++){
        dp[i][3] = (dp[i-3][1] + dp[i-3][2]) % mod;
        dp[i][2] = (dp[i-2][1] + dp[i-2][3]) % mod;
        dp[i][1] = (dp[i-1][2] + dp[i-1][3]) % mod;
    }
}

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

    calDP();

    int t;
    cin >> t;
    for(int T=0; T<t; T++){
        int a;
        cin >> a;

        cout << (dp[a][1] + dp[a][2] + dp[a][3]) % mod << '\n';
    }



    return 0;
}

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

1. 문제설명

한 번에 3가지 연산을 할 수 있다.

screen과 clipboard의 정보를 저장해서 BFS를 수행하면

원하는 이모티콘의 개수를 만들기 위한 최소 단계를 구할 수 있다.

2. 문제풀이코드 C++

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


int s;
struct Emoticon{
    int screen, copied;
};

int vis[MAX_NUM][MAX_NUM];

int BFS(int x){
    queue<Emoticon> Q;
    Q.push({1,0}); vis[1][0] = 1;

    while(!Q.empty()){
        auto cur = Q.front(); Q.pop();
        int curValue = vis[cur.screen][cur.copied];

        if(cur.screen == x){
            return curValue - 1;
        }


        //1. 클립보드에 복사하여 저장
        if(!vis[cur.screen][cur.screen]){
            vis[cur.screen][cur.screen] = curValue + 1;
            Q.push({cur.screen, cur.screen});
        }

        //2. 클립보드에 있는 모든 이모티콘을 화면에 붙여넣기 한다.,클립보드는 그대로 유지
        if(cur.screen+ cur.copied < MAX_NUM && !vis[cur.screen+cur.copied][cur.copied]){
            vis[cur.screen+cur.copied][cur.copied] = curValue + 1;
            Q.push({cur.screen + cur.copied, cur.copied});
        }

        //3. 화면에 있는 이모티콘 중 하나를 삭제한다.
        if(cur.screen-1 > 0 && !vis[cur.screen-1][cur.copied]){
            Q.push({cur.screen-1, cur.copied});
            vis[cur.screen-1][cur.copied] = curValue + 1;
        }

    }

    return -1;
}


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

    cin >> s;
    cout << BFS(s) << '\n';

    return 0;
}

나는 BFS로 이 문제를 풀었는데

DP로도 이 문제를 풀 수 있다.

BFS와 DP의 교집합에 놓인 문제라면

DP가 규칙만 빠르게 발견하면 훨씬 간결하게

풀 수 있는 장점이 있는 것 같다.

시간 절약을 위해 DP 공부를 더 해야할 필요가 있어보인다.

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

1.문제설명

에라토스테네스 체를 이용하여 미리 소수를 구분할 수 있는 배열을 만들어두고

입력받은 두 소수 A와 B에서

A를 시작점으로 하여 자리수를 하나씩 바꿔가면서 소수인지 판별하고 BFS를 돌면서

B로 도착할 수 있는지 확인하는 문제

다음 숫자를 구하는 식을 꼼꼼하게 잘 세워야 한다.

8033

1. 1000의 자리숫자 바꿔가면서 확인

0033 1033 2033 3033 4033 5033 6033 7033 8033 9033

2. 100의 자리숫자 바꿔가면서 확인

8033 8133 8233 ... 8933

3. 10의 자리 숫자 바꿔가면서 확인

8003 8013 8023 8033 ... 8093

4. 1의자리 숫자 바꿔가면서 확인

8030, 8031, 8032, ... 8039

즉 8033이 시작 숫자면

위의 모든 숫자를 한번 씩 보면서

소수인지 확인하고, 1000이상인지 확인하고, 이전에 방문했던 숫자인지 확인하여

BFS를 돌면 된다.

2.문제풀이코드 C++

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

bool Prime[10000];


void eratos(){
    fill(Prime, Prime+10000, 1);

    Prime[0] = 0; Prime[1] = 0;
    int sqrtn = int(sqrt(10000));

    for(int i=2; i<=sqrtn; i++){
        for(int j=i*i; j<10000; j+=i){
            Prime[j] = 0;
        }
    }
}


int BFS(int a, int b){
    if(a==b) return 0;

    int vis[10000];
    memset(vis, 0 , sizeof(vis));

    queue<int> Q;
    Q.push(a); vis[a] = 1;


    while(!Q.empty()){
        int cur = Q.front(); Q.pop();
        if(cur==b){
            return vis[cur]-1;
        }

        int minus = 1000;
        for(int i=0; i<4; i++){
            //숫자 계산 확인하기
            int minusedNum = cur - ((cur%(minus*10))/minus)*minus;

            for(int j=0; j<=9; j++){
                int nextNum = minusedNum + j*minus;

                if(Prime[nextNum] && vis[nextNum]==0 && nextNum>=1000){
                    vis[nextNum] = vis[cur] + 1;
                    Q.push(nextNum);
                }
            }
            minus/=10;
        }
    }
    return -1;
}

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

    int t;
    cin >> t;


    eratos();


    for(int T=0;T<t; T++){
        int a, b;
        cin >> a >> b;

        int tmp = BFS(a, b);

        if(tmp<0){
            cout <<"Impossible\n";
        }
        else{
            cout << tmp << '\n';
        }
    }

    return 0;
}

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

1. 문제설명

일반적인 BFS문제는 상하좌우로 네칸만 움직인다.

이 문제는 원숭이가 평소에는 상하좌우로 네칸을 움직일 수 있다가

K번의 기회로 말처럼 더 넓은 범위를 움직일 수 있다.

이런 문제를 표현하기 위해서는 최대 K번 말처럼 움직일 수 있으므로

현재까지 원숭이가 총 몇 번 말처럼 움직였는지 상태를 저장해줄 필요가 있다.

그래서 이러한 문제 유형을 나는 상태 추가 BFS라고 부르기로 했다.

그냥 저 혼자 부르는 거니까 다른데 가서 유식한 척 말하시면 안됩니다.

2. 상태추가?

왜 상태추가라고 하냐면

보통 일반적으로 BFS를 돌 때는

x,y 좌표를 방문했는지 여부를 저장하면서 중복된 행동을 하지 않도록 합니다.

이 문제도 단지 x,y좌표를 방문했는지 여부와 동일하게

x,y좌표 방문 여부 + '말처럼 움직인 횟수' 라는 상태가 추가되어

중복된 행동을 하지 않으면서 BFS를 돈다고 생각하면 편합니다.

그리고 또한 이 문제를 왜 BFS로 해결 할 수 있냐면

원하는 답이 원숭이가 총 몇번 움직이는 행동을 했는 지 구하는 것이기 때문에

말처럼 움직이든 원숭이처럼 움직이든 특정 행동엔 관심없고

움직임 단계별로 일정하게 증가시키면서 답을 구하면 되기 때문에

너비우선탐색으로 해결 할 수 있습니다.

3.문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;

struct Position {
    int x, y, k, d;

    Position(int a, int b, int c, int dd) {
        x = a, y = b, k = c, d = dd;
    }
};

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
//horse
int hdx[8] = {-2, -2, -1, -1, 1, 1, 2, 2};
int hdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};

queue<Position> Q;

int K, W, H;
int arr[203][203];
bool vis[203][203][32];


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

    cin >> K >> W >> H;

    // 행H , 열W
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cin >> arr[i][j];
        }
    }

    Q.push({0, 0, 0, 0});

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

        if (cur.x == H - 1 && cur.y == W - 1) {
            cout << cur.d << '\n';
            return 0;
        }

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

            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (vis[nx][ny][cur.k] || arr[nx][ny] == 1) continue;

            vis[nx][ny][cur.k] = 1;
            Q.push({nx, ny, cur.k, cur.d + 1});
        }

        if (cur.k + 1 <= K) {
            for (int i = 0; i < 8; i++) {
                int nx = cur.x + hdx[i];
                int ny = cur.y + hdy[i];

                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
                if (vis[nx][ny][cur.k + 1] || arr[nx][ny] == 1) continue;

                vis[nx][ny][cur.k + 1] = 1;
                Q.push({nx, ny, cur.k + 1, cur.d + 1});
            }
        }
    }

    cout << -1 << '\n';


    return 0;
}