입꼬리 올리고 사는 개발자

안녕하세요 오늘은 아침부터 예비군 통지서가 온 덕에 입꼬리가 내려가는 하루네요^^ 하하

단순 누적합 문제처럼 보이지만 고려할 부분이 많은 문제가 있어 하나 소개해드릴까 합니다. 그럼 시작해보죠!!

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

1. 문제

수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오.

즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다.

 (1 ≤ N ≤ 10^6, 2 ≤ M ≤ 10^3, 0 ≤ Ai ≤ 10^9)

2. 풀이

구간합이 M으로 나누어 떨어지는 경우의 수를 구하는 문제입니다.

가장 그리디한 풀이는 sum[i][j]라는 배열을 선언하고 모든 구간합을 구한 후 sum[i][j] % M = 0이 되는 경우의 수를 구하는 것일텐데요

골드 3 문제답게 10^6이라는 통 큰 N을 주면서 O(n^2)의 시간복잡도를 방지하였습니다.(prefix sum으로 1차원 배열을 하더라도 시간복잡도는 똑같겠네요).

핵심은 '모듈러 연산'이 0이 되는 경우의 수를 구하는 것입니다.

일단 prefix sum으로 sumarr[j] - sumarr[i-1]이 구간합이 되게끔 누적합을 모두 구해줍니다.

우리가 궁금한 것은 (sumarr[j] - sumarr[i-1]) % M = 0 이 되는 것인데

모듈러 연산은

(A + B) % C = (A % C + B % C) % C

(A - B) % C = (A % C - B % C) % C

가 성립합니다

따라서 (sumarr[j] - sumarr[i-1]) % M = 0 인 경우라면

(sumarr[j] % M - sum[i-1] % M) % M = 0이 될 것이고

저희는 sumarr[j] % M = sum[i-1] % M 인 경우의 수를 찾으면 되는 것입니다.

추가로 sumarr[j] % M = sum[i-1] % M 인 경우의 수는 서로 다른 두 누적합의 나머지가 같은 경우만 고려한 것이고

Ai 원소 하나로 M으로 나누어 떨어지는 경우의 수도 있으니 이 또한 추가로 더해줍니다.

3. 코드

//https://www.acmicpc.net/problem/10986
//10986. 나머지 합(Gold 3, 누적합)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;

ll N, M, ans = 0;
ll sumarr[1000000];
//sumarr의 나머지를 세는 배열
ll marr[1000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> M;

    //SOLVE
    //누적합 계산
    ll sum = 0;
    ll A;
    int cnt = 0;
    for(int i = 0; i < N; i++) {
        cin >> A;
        if(A % M == 0) cnt++;
        sum += A;
        sumarr[i] = sum;
    }

    //구간합 (sumarr[j] - sumarr[i-1]) & M = 0 이라면
    //(sumarr[j] % M) - (sumarr[i-1] % M) = 0 이므로 
    //(sumarr[j] % M) = (sumarr[i-1] % M)) 인 경우의 수를 찾자.
    for(int i = 0; i < N; i++) {
        marr[sumarr[i] % M]++;
    }
    for(int i = 0; i < M; i++) {
        //후보들 중 2개를 순서상관없이 고르는 경우의 수
        ans += marr[i] * (marr[i] - 1) / 2;
    }
    //marr[0]에 들어갔던 구간합은 자기 자신만으로도 해당되기 때문에 따로 더해줌
    ans += marr[0]; 

    //OUTPUT
    cout << ans;
}

4. 이모저모

개인적으로 여러번 실수했던 부분이 있습니다.

바로 나머지를 세주는 marr의 자료형을 int로 선언하여 오버플로우가 계속 발생한 것입니다.

marr를 int로 선언한 배경은 marr의 원소가 한곳에 몰려서 아무리 커봤자 N의 최대값인 10^6을 넘지 못하기 때문에

int로도 충분하다고 생각하였습니다. 

하지만 ans += marr[i] * (marr[i] - 1) / 2; 이 계산에서 int 범위를 넘기기 때문에 오버플로우가 발생한다는 사실을 백준 질문게시판을 통해 알게되었고 굳이 int를 쓰고 싶다면 저 계산식에서만

1LL * 을 더해주거나 int64_t(marr[i]) 등의 형 변환을 해주어야 한다는 것도 배웠습니다.

누적합 + 모듈러 연산의 성질 + 자료형 등등 많은 것을 배울 수 있는 문제였습니다.오늘 하루도 화이팅 하십쇼~~!!

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

안녕하세요 오랜만에 오랫동안 고민한 문제가 있어 가지고 왔습니다

1. 문제

5개의 식당을 최단 거리로 방문해야 하는 문제입니다

2. 풀이

BFS와 완전탐색이 결합된 문제입니다.

BFS로 최대 20개의 식당 + 시작점 간의 모든 거리를 구해준 후(21 x 21)

DFS를 통해 모든 순서를 고려하여 최단거리를 구해주면됩니다. (순서를 고려하여 5가지를 고르는 경우의 수 -> 순열 20P5)

BFS에서 저는 기본적인 실수를 하였는데 시간이 아슬아슬한 완전탐색 문제이니 만큼

첫번째 가게에서 두번째 가게로 가는 최단 거리, 세번째 가게로 가는 최단 거리 ...를 따로따로 21x21번 구하면 시간 초과가 납니다.

한 가게를 기준으로 명확히 잡고 BFS로 구한 거리를 모든 가게에 적용시켜 주어야 합니다.

3. 코드

//https://www.acmicpc.net/problem/23817
//23817. 포항항(Gold 1, BFS, 브루트포스)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long
using namespace std;

int N, M, ans = INT_INF;
int board[1000][1000]; //입력받을 때 int로 변환해서 받기
int m_dist[1000][1000];
int r_dist[21][21]; //식당과 식당간의 거리, 0번째는 시작점으로 가정
vector<pair<int, int> > restaurant; //식당 좌표들
int rc = 0; //식당 개수 시작점은 제외
bool visited[1000][1000];
bool rvisited[21]; //식당 방문여부
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

void bfs(int sr) {
    memset(visited, 0, sizeof(visited));
    queue<pair<int, int> > q;
    q.push(make_pair(restaurant[sr].first, restaurant[sr].second));
    
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            m_dist[i][j] = INT_INF;
        }
    }
    visited[restaurant[sr].first][restaurant[sr].second] = 1;
    m_dist[restaurant[sr].first][restaurant[sr].second] = 0;

    while(!q.empty()) {
        int cx = q.front().first;
        int cy = q.front().second;
        q.pop();

        for(int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(visited[nx][ny] || board[nx][ny] == -1) continue;
            //최소 거리 갱신
            m_dist[nx][ny] = m_dist[cx][cy] + 1;
            visited[nx][ny] = 1;
            q.push(make_pair(nx, ny));
        }
    }

    //한 가게를 기준으로 구한 모든 칸에 대한 최소거리를
    //식당에 관해서만 다루는 배열에 적용하기
    for(int i = 0; i <= rc; i++) {
        if(m_dist[restaurant[i].first][restaurant[i].second] == INT_INF) r_dist[sr][i] = -1;
        else r_dist[sr][i] = m_dist[restaurant[i].first][restaurant[i].second];
    }
    return;
}

void dfs(int sr, int cnt, int dist) {
    if(cnt == 5) {
        ans = (ans > dist) ? dist : ans;
        return;
    }
    
    //백트래킹 해주면서 모든 경우의 수를 탐방
    for(int i = 1; i <= rc; i++) {
        if(!rvisited[i] && r_dist[sr][i] >= 1) {
            rvisited[i] = 1;
            dfs(i, cnt + 1, dist + r_dist[sr][i]);
            rvisited[i] = 0;
        }
    }
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> M;
    char c;
    restaurant.push_back(make_pair(0, 0));
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < M; j++) {
            cin >> c;
            if(c == 'X') board[i][j] = -1;
            else if(c == 'K') {
                board[i][j] = ++rc;
                restaurant.push_back(make_pair(i, j));
            }
            else if(c == 'S') {
                restaurant[0] = make_pair(i, j);
            }
        }
    }

    // SOLVE
    //한 식당을 기준으로 식당 간의 최소거리 구하기
    memset(m_dist, 0, sizeof(m_dist));
    for(int i = 0; i <= rc; i++) {
        bfs(i);
    }
    
    rvisited[0] = 1;
    dfs(0, 0, 0); //현재 가게, 들린 가게 수, 현재까지의 거리;

    //OUTPUT
    if(ans == INT_INF) ans = -1;
    cout << ans;
}

4. 이모저모

이제 BFS 정도 문제는 쉽다라고 자만한 저를 당황시킨 문제였습니다.

전체 보드도 1000 x 1000로 큰데다가 20P5라는 큰 경우의 수를 보고 완전 탐색이라고 생각하기 힘들었습니다.

난이도가 올라갈 수록 여러가지 개념이 섞인 문제(그래프 탐색에 투포인터가 섞인다던가..)가 나올텐데 더 고심해봐야겠다는 생각을 했습니다.

오늘 하루도 입꼬리 올리는 하루가 되시길 바랍니다!!

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

안녕하세요 오랜만에 포스팅 남깁니다.

이번 문제는 해결방법을 떠올리는 것은 쉽지만 구현이 많고 복잡한 부분이 있기에 Gold 2라는 난이도가 책정된 것 같습니다.

한번 보시죠!

1. 문제

재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하나의 말 위에 다른 말을 올릴 수 있다. 체스판의 각 칸은 흰색, 빨간색, 파란색 중 하나로 색칠되어있다.

게임은 체스판 위에 말 K개를 놓고 시작한다. 말은 1번부터 K번까지 번호가 매겨져 있고, 이동 방향도 미리 정해져 있다. 이동 방향은 위, 아래, 왼쪽, 오른쪽 4가지 중 하나이다.

턴 한 번은 1번 말부터 K번 말까지 순서대로 이동시키는 것이다. 한 말이 이동할 때 위에 올려져 있는 말도 함께 이동하며, 가장 아래에 있는 말만 이동할 수 있다. 말의 이동 방향에 있는 칸에 따라서 말의 이동이 다르며 아래와 같다. 턴이 진행되던 중에 말이 4개 이상 쌓이는 순간 게임이 종료된다.

• A번 말이 이동하려는 칸이
  • 흰색인 경우에는 그 칸으로 이동한다. 이동하려는 칸에 말이 이미 있는 경우에는 가장 위에 A번 말을 올려놓는다.
    • A번 말의 위에 다른 말이 있는 경우에는 A번 말과 위에 있는 모든 말이 이동한다.
    • 예를 들어, A, B, C로 쌓여있고, 이동하려는 칸에 D, E가 있는 경우에는 A번 말이 이동한 후에는 D, E, A, B, C가 된다.
  • 빨간색인 경우에는 이동한 후에 A번 말과 그 위에 있는 모든 말의 쌓여있는 순서를 반대로 바꾼다.
    • A, B, C가 이동하고, 이동하려는 칸에 말이 없는 경우에는 C, B, A가 된다.
    • A, D, F, G가 이동하고, 이동하려는 칸에 말이 E, C, B로 있는 경우에는 E, C, B, G, F, D, A가 된다.
  • 파란색인 경우에는 A번 말의 이동 방향을 반대로 하고 한 칸 이동한다. 방향을 반대로 한 후에 이동하려는 칸이 파란색인 경우에는 이동하지 않고 방향만 반대로 바꾼다.
  • 체스판을 벗어나는 경우에는 파란색과 같은 경우이다.

체스판의 크기와 말의 위치, 이동 방향이 모두 주어졌을 때, 게임이 종료되는 턴의 번호를 구해보자.

문제가 그림과 봐야 좋을 듯 하니 링크에서 보시는 걸 추천드립니다^^

2. 풀이

풀이는 간단합니다.

체스판의 최대 크기가 12 x 12, 체스말의 최대 개수가 10, 반복횟수가 최대 1000번 이기 때문에 시간복잡도를 고려하지 않고 구현을 해주면 되겠습니다.

한 턴을 쓸 때마다 모든 체스말을 체크해주어야 하며 그 중에서도 해당 체스말이 가장 아래에 존재할 때만 이동이 가능합니다.

제가 고려한 순서는 이러한데요.1. 이동할 칸이 blue거나 체스판 밖이라면 방향 전환 후 다음 이동할 칸이 어디인지 체크 후 또 다시 blue거나 체스판 밖이라면 다음 체스말 차례로(고려할 필요가 없다면 2, 3번으로)2. 이동할 칸이 white라면 이동3. 이동할 칸이 red라면 역순으로 재정렬 후 이동4. 이동 완료 후 해당 칸의 높이가 4이상인지 확인

3. 코드

코드가 좀 길지만 함수별로 어떤 동작을 하는지 보시면 조금은 편하실 겁니다. 너저분한 코드라 죄송합니다..

//https://www.acmicpc.net/problem/17780
//17780. 새로운 게임(Gold 2, 구현)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int N, K, ans = 0;
int direction[11]; //체스말의 이동방향
pair<int, int> p[11]; //체스말의 위치
int color[13][13]; //체스칸의 색깔
int height[13][13]; //체스칸의 말의 높이
int sq_arr[13][13][11]; //해당 체스칸의 체스말 배열
//idx순서대로 1은 우향, 2는 좌향, 3은 북향, 4는 남향
int dx[5] = {0, 0, 0, -1, 1};
int dy[5] = {0, 1, -1, 0, 0};
int a_flag = 0; //a_flag는 높이가 4 이상인게 생겼는지 체크,

void reverse(int x, int y) {
    if(height[x][y] <= 1) return;
    for(int i = 0; i < height[x][y] / 2; i++) {
        int tmp = sq_arr[x][y][i];
        sq_arr[x][y][i] = sq_arr[x][y][height[x][y] - 1 - i];
        sq_arr[x][y][height[x][y] - 1 - i] = tmp;
    }
}

void white(int x, int y, int nx, int ny) {
    for(int i = height[nx][ny]; i < height[nx][ny] + height[x][y]; i++) {
        //복사
        sq_arr[nx][ny][i] = sq_arr[x][y][i - height[nx][ny]];
    }
    //체스말 위치 변경 + 원래 칸 초기화 
    for(int i = 0; i < height[x][y]; i++) {
        p[sq_arr[x][y][i]].first = nx;
        p[sq_arr[x][y][i]].second = ny;
        sq_arr[x][y][i] = 0;
    }
    height[nx][ny] += height[x][y];
    height[x][y] = 0;
    if(height[nx][ny] >= 4) a_flag = 1;
}

void red(int x, int y, int nx, int ny) {
    //순서를 뒤집은 후에 그대로 옮겨주면 되므로, 본인 칸에서 순서 뒤집기 -> white()
    reverse(x, y);
    white(x, y, nx, ny);
}

void blue(int k) {
    if(direction[k] == 1) direction[k] = 2;
    else if(direction[k] == 2) direction[k] = 1;
    else if(direction[k] == 3) direction[k] = 4;
    else if(direction[k] == 4) direction[k] = 3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    memset(height, 0, sizeof(height));
    memset(sq_arr, 0, sizeof(sq_arr));
    cin >> N >> K;
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            cin >> color[i][j];
        }
    }
    //체스말의 위치와 방향 입력 후 체스칸에도 반영해주기
    for(int i = 1; i <= K; i++) {
        int tx, ty;
        cin >> tx >> ty >> direction[i];
        p[i].first = tx, p[i].second = ty;
        sq_arr[tx][ty][0] = i;
        height[tx][ty] = 1;
    }

    //SOLVE
    while(true) {
        ans++;
        //모든 말을 한번씩
        for(int i = 1; i <= K; i++) {
            int x = p[i].first;
            int y = p[i].second;
            //만약 현재 움직여야할 체스말이 가장 아래에 있는 것이 아니라면 skip
            if(sq_arr[x][y][0] != i) continue;

            int nx = x + dx[direction[i]];
            int ny = y + dy[direction[i]];

            //갈 곳이 blue 혹은 체스판 밖이라면
            if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                //방향 바꿔주기
                blue(i);
                nx = x + dx[direction[i]];
                ny = y + dy[direction[i]];
                //blue 바꿔준 후에도 blue가 나온 것이기 때문에 그냥 넘겨준다.
                if(nx < 1 || nx > N || ny < 1 || ny > N || color[nx][ny] == 2) {
                    continue;
                }
            }

            //갈 곳이 white라면
            if(color[nx][ny] == 0) {
                white(x, y, nx, ny);
            }
            //갈 곳이 red라면
            else if(color[nx][ny] == 1) {
                red(x, y, nx, ny);
            }

            if(a_flag) break;
        }
        //4이상이면 종료
        if(a_flag || ans > 1000) break;
    }

    //OUTPUT
    if(ans > 1000) ans = -1;
    cout << ans;
}

이런 문제는 디버깅이 오래 걸리는데 테케를 몇개를 해봐도 다 맞게 나와서 2시간이나 걸린 문제였네요.

white 함수에서 이동할 칸의 높이가 0인 경우를 괜히 구분했다가 오류잡는 데 힘들었습니다 하하

오랜만에 입꼬리가 내려갈 뻔했지만 읽으시는 분들 스마일한 하루 되시고

struct, vector를 사용하면 더 깔끔한 코드가 될 듯 하니 도전해보세용~@!

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

안녕하세요 오늘은 만만하게 보던 그리디 + 저의 절반 나이일 초등부 올림피아드 문제였지만

고민끝에 다른 분의 코드를 참고하게 된 좋은 문제가 있어 가지고 왔습니다.

난이도는 Gold 2입니다!

1. 문제

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓을 수 있고, 다른 쪽에는 무게를 측정하려는 물건만 올려놓을 수 있다.

무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.

예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 

2. 풀이

<< 첫 째 줄에는 저울추의 개수를 나타내는 양의 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 둘째 줄에는 저울추의 무게를 나타내는 N개의 양의 정수가 빈칸을 사이에 두고 주어진다. 각 추의 무게는 1이상 1,000,000 이하이다. >>

라는 조건이 있었음에도 O(n^2)의 방법만을 고려하고 메모리 초과라는 문제와 씨름하다가

다른 블로그의 코드 전역변수에 int arr[1000]만이 있는 것을 보고 선형적 방법을 찾기 위해 노력했습니다.

풀이방법은 

주어진 무게 추 weight들을 오름차순으로 정렬한 뒤

(0번째 무게추부터 k번째 무게추의 합 + 1보다, k+1번째 추의 무게가 더 클 때 라는 의미)

를 만족하는 최초의 k번째 무게 추를 구하고 k번째 무게추까지의 합 + 1이 정답이 됩니다.

풀이방법을 예시에 적용시켜 보면

(1) 오름차순 정렬 -> 1, 1, 2, 3, 6, 7, 30

(2) 다음 무게추의 합이 이전 무게추들의 합 + 1보다 커지는 지점을 발견 1+1+2+3+6+7 + 1 < 30

(3) 정답은 1+1+2+3+6+7+1 = 21

아래 코드를 보시면 더 이해가 잘 되실 겁니다

(무게가 1인 무게추가 없는 경우와 마지막 무게추까지 도달할 수 있는 경우 포함)

3. 코드

//https://www.acmicpc.net/problem/2437
//2437. 저울(Gold 2, 그리디)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long

using namespace std;

int N, ans = 1;
int weight[1000];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N;
    for(int i = 0; i < N; i++) cin >> weight[i];

    //SOLVE
    sort(weight, weight + N);
    if(weight[0] > 1) ans = 1;
    else {
        int total = weight[0];
        for(int i = 1; i < N; i++) {
            if(total + 1 < weight[i]) {
                ans = total + 1;
                break;
            }
            total += weight[i];
            //마지막까지 당도한다면
            if(i == N - 1) ans = total + 1;
        }
    }

    //OUTPUT
    cout << ans;
}

남은 설 연휴까지 퐈이팅하시고 오늘도 웃는 하루 되시길 바랍니다~~!!

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

안녕하세요 오늘도 DP 문제로 돌아왔습니다

1. 문제

알파벳 소문자로 구성된 길이 1 이상의 두 문자열 X, Y가 있다. 이 문자열들의 임의의 위치에 공백을 삽입하여 두 문자열의 길이를 같게 만든 다음, 앞에서부터 한 글자씩 살펴보면서, 같은 위치에 있는 두 문자 X[i], Y[i]에 대해서 다음과 같이 점수를 계산한다.

1. 두 문자가 같은 경우에는 A(> 0)점을 받게 된다. 단, 두 문자가 모두 공백인 경우는 허용되지 않는다.
2. 두 문자 중 적어도 하나가 공백인 경우에는 B(< 0)점을 받게 된다.
3. 두 문자가 모두 공백이 아니고 서로 다른 경우에는 C(< 0)점을 받게 된다.

예를 들어 A = 10, B = -1, C = -5인 경우, 다음과 같은 경우들을 살펴보자.

2. 풀이

한번의 계산에는 세가지 경우의 수가 존재합니다.

1. 둘 다 문자를 고르는 경우(점수는 두가지 경우가 있음).

2. 첫 문자열에서는 문자, 두번째 문자열에서는 공백을 고르는 경우.

3. 첫 문자열에서는 공백, 두번째 문자열에서는 문자를 고르는 경우.

따라서 Score[i][j]를 첫번째 문자열 i번째 문자, 두번째 문자열 j번째 문자까지 왔을 때의 최대 점수라고 한다면(아직 문자를 사용하지 않은)

1. Score[i-1][j-1] + (A or C)(i-1번째 문자와 j-1번째 문자가 같다면 A, 다르다면 C)

2. Score[i-1][j] + B

3. Score[i][j-1] + B

중 최대값이 Score[i][j]가 되겠습니다.

3. 코드

Bottom-up 방식입니다.

dp[i][j]의 의미는 위 Score[i][j]와 동일하게 i번째 문자, j번째 문자까지 왔을 때의 최대 점수입니다.

문자열은 0번째 부터 시작하기 때문에 위 예시에 따르면 최종 정답은 a, b, c를 모두 소모하고 d, c를 모두 소모한 후인

최종 정답은 dp[3][2]가 되겠습니다.(dp[2][1]이 아님을 주의)

//https://www.acmicpc.net/problem/2216
//2216. 문자열과 점수(Gold 3, DP)

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long

using namespace std;

int N;
string str1, str2;
int str1_len, str2_len;
ll dp[3001][3001];
int A, B, C;
ll ans = -LL_INF;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> A >> B >> C;
    cin >> str1 >> str2;

    //SOLVE
    str1_len = str1.length(), str2_len = str2.length();
    for(int i = 0; i < 3001; i++) {
        for(int j = 0; j < 3001; j++) {
            dp[i][j] = -LL_INF;
        }
    }

    dp[0][0] = 0;
    for(int i = 0; i < str1_len + 1; i++) {
        for(int j = 0; j < str2_len + 1; j++) {
            if(i > 0 && j > 0) {
                int tscore = (str1[i-1] == str2[j-1]) ? A : C;
                dp[i][j] = max(dp[i][j], dp[i-1][j-1] + tscore);
            }
            if(j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j-1] + B);
            }
            if(i > 0) {
                dp[i][j] = max(dp[i][j], dp[i-1][j] + B);
            }
        }
    }
    
    //OUTPUT
    cout << dp[str1_len][str2_len];
}

아래는 Top-down 방식입니다.

ll cal(int idx1, int idx2) {
    if(idx1 == str1_len && idx2 == str2_len) return 0;
    
    ll &ret = dp[idx1][idx2];
    if(ret != -LL_INF) return ret;

    ret = -LL_INF;
    ll score;

    //둘 다 문자 선택
    if(idx1 < str1_len && idx2 < str2_len) {
        score = (str1[idx1] == str2[idx2]) ? A : C;
        ret = max(ret, score + cal(idx1+1, idx2+1));
    }

    //str1은 문자, str2는 공백 선택
    score = B;
    if(idx1 < str1_len) ret = max(ret, score + cal(idx1+1, idx2));

    //str1은 공백, str2는 문자 선택
    score = B;
    if(idx2 < str2_len) ret = max(ret, score + cal(idx1, idx2+1));

    return ret;
}

//cout << cal(0, 0)

부족한 글 읽어주셔서 감사합니다. 지적, 질문 모두 환영입니다.

오늘 하루 웃음이 가득하시길~!!

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

안녕하세요 블로그 첫 글이네요 하하하 오늘은 DP를 활용한 Gold 2 문제 케익 배달을 풀어보았습니다.

1. 문제

프랑스에서 공부를 하고 돌아온 선아는 자신이 그렇게도 되고 싶어 했던 파티셰가 되었다. 케익 배달 전문업체 보나뻬띠에 취직한 선아는 친절하게도 자신이 만든 케익을 고객들에게 직접 배달을 하려 한다. N명의 고객에게 케익을 배달하는데 주문이 들어온 순서대로 배달하기를 원하며 고객이 케익을 받을 수 있을 만큼 충분히 가까이까지 배달한다.

N명의 고객의 위치는 순서대로 100,000×100,000 격자의 정수 좌표로 주어지고 처음 출발하게 되는 보나뻬띠의 위치도 정수 좌표로 주어진다. 선아는 격자 위에서 상하좌우로만 움직이며 고객에게 케익을 전달하기 위해서는 그 고객의 위치까지 가거나 고객의 상하좌우 인접 격자점에 가야 한다. 이때 선아가 최단거리를 이동하여 입력된 순서대로 배달을 끝낼 수 있는 거리를 계산하는 프로그램을 작성하시오. 여기서 거리는 격자 상의 칸 수를 말한다.

위의 예에서 선아는 11칸을 움직여서 세 명의 고객에게 배달을 마칠 수 있다. 선아는 반드시 고객들에게 순서대로 배달을 하며 순서에 어긋난 사람에게 배달을 할 수 있는 위치에 있더라도 케익을 주지 않고 순서대로 배달을 한다. 고객의 위치는 중복이 될 수도 있다.

2. 풀이

좌표평면 상의 최단거리를 구하는 문제이기 때문에 기본적으로 DFS, BFS를 떠올릴 수 있습니다만 

단순 그래프 탐색을 한다면 한 고객 당 고려해야 할 지점이 5개이기 때문에 대강 O(5^n) 이라는 어마무시한 exponential 시간 복잡도가 기다리고 있겠습니다.

여기서 핵심은 현재 고객 주위 5지점에서 다음 고객 주위 5지점 까지의 경우의 수는 25가지이고 이 값은 고정적이기 때문에 이를 dp 배열에 저장해두면 중복 계산을 피할 수 있습니다.

3. 코드

아래 코드는 Top-down 방식이며

dp[idx][n]은 idx번째 고객 주위 n번째 지점에서 부터 마지막까지 배달하는 최소 경로의 길이 입니다.

//https://www.acmicpc.net/problem/2159
//2159. 케익 배달(Gold2, DP, DFS) 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>

#define endl "\n"
#define INT_INF 2147483647
#define LL_INF 9223372036854775807
#define ll long long

using namespace std;

int N;
pair<int, int> loc[100001];
int dx[5] = {0, 1, -1, 0, 0};
int dy[5] = {0, 0, 0, 1, -1};
ll dp[100001][5];

ll cal(int x, int y, int idx, int n) {
    if(idx == N) return 0;
    ll &ret = dp[idx][n];
    if(ret != -1) return ret;

    ret = LL_INF;
    
    for(int i = 0; i < 5; i++) {
        int nx = loc[idx + 1].first + dx[i];
        int ny = loc[idx + 1].second + dy[i];
        if(nx < 1 || nx > 100000 || ny < 1 || ny > 100000) continue;
        int dist = abs(nx - x) + abs(ny - y);
        ret = min(ret, dist + cal(nx, ny, idx + 1, i));
    }

    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    freopen("input.txt", "r", stdin);

    //INPUT
    cin >> N >> loc[0].first >> loc[0].second;

    for(int i = 1; i <= N; i++) {
        cin >> loc[i].first >> loc[i].second;
    }

    //SOLVE
    memset(dp, -1, sizeof(dp));
    cout << cal(loc[0].first, loc[0].second, 0, 0);

    //OUTPUT
}

아래 코드는 Bottom-up 방식이며 

dp[idx][n]은 idx번째 고객 주위 n번째 지점까지 가는 최소 경로의 길이입니다.

    memset(dp, 0, sizeof(dp));
    for(int i = 1; i <= N; i++) {
        for(int j = 0; j < 5; j++) {
            dp[i][j] = LL_INF;
            for(int k = 0; k < 5; k++) {
                int cx = loc[i].first + dx[j];
                int cy = loc[i].second + dy[j];
                int px, py;
                if(i == 1) {
                    px = loc[i-1].first;
                    py = loc[i-1].second;
                } else {
                    px = loc[i-1].first + dx[k];
                    py = loc[i-1].second + dy[k];
                }
                if(cx < 1 || cx > 100000 || cy < 1 || cy > 100000) continue;
                if(px < 1 || px > 100000 || py < 1 || py > 100000) continue;
                dp[i][j] = min(dp[i][j], dp[i-1][k] + abs(cx - px) + abs(cy - py));
            } 
        }
    }

    //OUTPUT
    ll ans = LL_INF;
    for(int i = 0; i < 5; i++) {
        ans = min(ans, dp[N][i]);
    }
    cout << ans;

부족한 첫글 읽어주셔서 감사하고 

화끈한 지적이나 질문 언제든 환영합니다 감사합니다~!