입꼬리 올리고 사는 개발자

안녕하세요 오늘은 이분탐색과 그의 bound 전우들에 대해 알아보겠습니다!

1. 이분탐색

이분 탐색 알고리즘(binary search algorithm)은 이진 탐색 알고리즘이라고도 불리며 

오름차순으로 정렬된 리스트(배열)에서 특정한 값의 위치를 찾는 알고리즘입니다.

그럼 예시와 함께 이분탐색의 장단점에 대해 알아보겠습니다.

운이 좋게도 정렬된 배열의 특정한 값의 위치를 찾는 가장 단순한 방법은 앞에서 부터 비교하는 것입니다

값이 10인 데이터의 위치를 찾는 다고 가정해보면

for(int i = 0; i < N; i++) {
	if(arr[i] == 16) return i;
}

0번째 원소부터 차근차근 비교해보면서 7번의 비교를 끝내고 나서야 10이 idx = 6의 위치에 있다는 것을 알 수 있습니다.

최악의 경우 크기가 N인 배열에서는 N번의 비교가 필요한 선형적인 탐색이므로 O(n)의 시간이 걸릴 것 입니다.

여기서 이분 탐색을 이용하여 더 효율적이라 볼 수 있는 O(logN)의 시간도 가능합니다.

이분 탐색의 핵심은 한 번의 비교로 데이터를 반으로 나눠(둘 이, 나눌 분 해서 이분) 우리가 고려해야 할 구간의 크기를 반으로 줄이는 것입니다.

이제 10의 위치를 이분 탐색을 통하여 찾아봅시다!!

먼저 배열의 가장 첫번째 인덱스를 low(고려해야 할 구간의 처음), 가장 마지막 인덱스를 high(고려해야할 구간의 끝)로 설정해줍니다.

그 후 그 가운데 인덱스인 (low + high)  / 2  를 mid로 지정해 줍니다. 예시의 경우에는 4가 되겠습니다.

그 후 arr[mid]값과 우리가 찾고 있는 값의 대소 비교를 해줍니다.

arr[mid]값인 6은 우리가 찾는 값은 10보다 작습니다. 그리고 low부터 mid 까지의 값은 모두 6보다 작거나 같은 값들입니다.

이 의미는 low부터 mid까지의 값들은 모두 10보다도 작을 것이기 때문에 이 구간은 10이 있을 수 없다는 것입니다.

이제 필요없는 구간들을 제외하고 탐색할 구간을 재설정 해 줍니다.

고려해야할 구간의 처음인 low를  mid의 바로 오른쪽인 mid + 1로, 고려해야할 구간의 가장 끝인 high는 그대로 둡니다.

또 다시 mid는 중간에 위치한 값인 (low + high) / 2 로 설정해 줍니다.

우리는 이 과정을 arr[mid]가 찾는 값(10)이 나올 때 까지 반복해줄 것입니다.

이번의 arr[mid]값인 13은 우리가 찾는 10보다 크기 때문에 mid부터 오른쪽 값들은 10이 없는 것이 확정입니다.

이제 다시 low는 5 그대로 high는 6으로 설정해 준 뒤 mid는 (5 + 6) / 2 인 5로 설정해줍니다.

arr[mid]값인 8이 10보다 작으므로 low부터 mid까지의 구간을 폐쇄하고 low를 6 high를 6 mid를 (6 + 6) / 2인 6으로 재설정합니다.

우리가 찾는 값인 10이 arr[mid]와 일치하므로 10의 위치는 idx = 6이었습니다.

이와 같이 이분탐색은 low, high, mid를 재설정해주며 고려해야할 구간을 줄여가고

최종적으로는 arr[mid] = 찾는 값이 되는 mid를 찾는 알고리즘입니다.

코드는 이러합니다.

int binarySearch(int arr[], int low, int high, int target){
    while(low <= high){
        int mid = (low + high) / 2;
        if(arr[mid] == target) return mid;
        //target보다 크다면 오른쪽 구간은 필요없음
        if(arr[mid] > target) high = mid - 1;
        //target보다 작다면 왼쪽 구간은 필요없음
        else low = mid + 1;
    }
    return -1;
}

이분탐색의 장점 - 원하는 원소를 O(log n) 시간에 찾을 수 있다.

이분탐색의 단점 - 정렬된 리스트에만 사용할 수 있다(정렬도 O(log n)이라 생각하면 시간복잡도의 변화는 없다)

2. Upper Bound & Lower Bound

이분 탐색은 특정한 한 데이터를 찾는 데에 좋지만 우리 실생활에서는 한번에 여러 데이터가 필요할 때가 있습니다.

예를 들어 상대평가로 학점 컷을 나눌 때 90점 이상인 학생 모두를 A로 하려 한다든가

중복이 허용되는 데이터에서 생일이 9월 22일인 모든 데이터가 필요한 경우 등등이 있습니다.(이분 탐색은 9월 22일이 생일인 데이터, 즉 인덱스 하나만을 반환함).

이런 경우들은 이분 탐색의 Bound 형제들이 요긴하게 쓰입니다.

Upper Bound는 특정 값 '초과'의 값이 처음으로 나타나는 위치를 뜻하며

Lower Bound는 특정 값 '이상'의 값이 처음으로 나타나는 위치를 뜻합니다.

이런 리스트에서 '1' 이란 값의 Upper Bound와 Lower Bound를 찾는다면

Upper Bound는 '1' 초과인 값이 처음으로 나타나는 '3'의 위치인 5

Lower Bound는 '1' 이상인 값이 처음으로 나타나는 '1'의 위치 2입니다.

'5'라는 값의 Upper Bound와 Lower Bound도 찾아보죠

Upper Bound는 '5' 초과인 값이 처음으로 나타나는 '6'의 위치인 8

Lower Bound는 '5' 이상인 값이 처음으로 나타나는 '6'의 위치 8입니다.

이처럼 Upper Bound와 Lower Bound는 서로 같을 수도 있습니다.

이를 활용하는 방법은 여러가지가 있습니다.

값이 1을 초과하는 데이터들 ->1의 Upper Bound 부터 데이터 끝까지

값이 5 미만의 데이터 -> 0 부터 5의 Lower Bound - 1 까지

값이 1인 데이터들 -> 1의 Lower Bound부터 1의 Upper Bound - 1까지

등등이 있겠습니다

찾는 과정은 이분탐색과 상당히 흡사하기 때문에 코드와 주석으로 대체하겠습니다.

초과, 이상의 차이인 만큼 조건문의 등호 하나만 차이가 나는 것을 볼 수 있습니다.

int UpperBound(int arr[], int low, int high, int target){
    while(low < high){
        int mid = (low + high) / 2;
        //arr[mid]값이 target 초과라면 high 뒤의 값들은 최초로 초과이진 않을 것임 
        if(arr[mid] > target) high = mid;
        //arr[mid]값이 target 이하라면 low부터 mid까지는 모두 target 이하일 것임
        else low = mid + 1;
    }
    //구간 내의 모든 값이 target 이하라면 마지막 + 1 위치 반환
    return high + 1;
}

int LowerBound(int arr[], int low, int high, int target){
    while(low < high){
        int mid = (low + high) / 2;
        //arr[mid]값이 target 이상이라면 high 뒤의 값들은 최초로 이상이진 않을 것임 
        if(arr[mid] >= target) high = mid;
        //arr[mid]값이 target 미만이라면 low부터 mid까지는 모두 target 미만일 것임
        else low = mid + 1;
    }
    //구간 내의 모든 값이 target 미만이라면 마지막 + 1 위치 반환
    return high + 1;
}

* 개인적인 팁이라면 리스트 전체를 탐색하기 위해서는 high를 N-1이 아닌 N으로 설정하는 것이 좋습니다.

1.  만약 끝값이 배열 내 유일한 7이라고 했을 때 7의 Lower Bound는 N-1, Upper Bound가 N이 나오게끔 설정하는 방법

2. N이 mid값이 되는 경우는 절대 존재할 수 없으므로 seg fault도 일어나지 않음.

Upper Bound와 Lower Bound는 <Algorithm> 헤더에도 구현되어 있습니다.

정렬은 필수로 해주시고 이 함수들은 주소값 자체를 반환하기 때문에 arr[0]의 주소값을 빼주셔야 인덱스를 구할 수 있습니다.

추가로 배열 내에 Upper Bound, Lower Bound가 존재하지 않는 경우는 N을 반환합니다.

upper_bound(arr, arr + N, target) - arr  

lower_bound(arr, arr + N, target) - arr  

https://cplusplus.com/reference/algorithm/upper_bound/

https://cplusplus.com/reference/algorithm/lower_bound/

* 표시된 팁이 알고리즘 문제들 풀 때 알짜배기라고 생각합니다.

이번 주도 화이팅입니다!!

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;

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

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