오늘의 문제
혼자서 하는 틱택토
미로 탈출
이모티콘 할인행사
택배 배달과 수거하기

혼자서 하는 틱택토

문제 설명
틱택토는 두 사람이 하는 게임으로 처음에 3x3의 빈칸으로 이루어진 게임판에 선공이 "O", 후공이 "X"를 번갈아가면서 빈칸에 표시하는 게임입니다. 가로, 세로, 대각선으로 3개가 같은 표시가 만들어지면 같은 표시를 만든 사람이 승리하고 게임이 종료되며 9칸이 모두 차서 더 이상 표시를 할 수 없는 경우에는 무승부로 게임이 종료됩니다.

할 일이 없어 한가한 머쓱이는 두 사람이 하는 게임인 틱택토를 다음과 같이 혼자서 하려고 합니다.

• 혼자서 선공과 후공을 둘 다 맡는다.
• 틱택토 게임을 시작한 후 "O"와 "X"를 혼자서 번갈아 가면서 표시를 하면서 진행한다.

틱택토는 단순한 규칙으로 게임이 금방 끝나기에 머쓱이는 한 게임이 종료되면 다시 3x3 빈칸을 그린 뒤 다시 게임을 반복했습니다. 그렇게 틱택토 수 십 판을 했더니 머쓱이는 게임 도중에 다음과 같이 규칙을 어기는 실수를 했을 수도 있습니다.

• "O"를 표시할 차례인데 "X"를 표시하거나 반대로 "X"를 표시할 차례인데 "O"를 표시한다.
• 선공이나 후공이 승리해서 게임이 종료되었음에도 그 게임을 진행한다.

게임 도중 게임판을 본 어느 순간 머쓱이는 본인이 실수를 했는지 의문이 생겼습니다. 혼자서 틱택토를 했기에 게임하는 과정을 지켜본 사람이 없어 이를 알 수는 없습니다. 그러나 게임판만 봤을 때 실제로 틱택토 규칙을 지켜서 진행했을 때 나올 수 있는 상황인지는 판단할 수 있을 것 같고 문제가 없다면 게임을 이어서 하려고 합니다.

머쓱이가 혼자서 게임을 진행하다 의문이 생긴 틱택토 게임판의 정보를 담고 있는 문자열 배열 board가 매개변수로 주어질 때, 이 게임판이 규칙을 지켜서 틱택토를 진행했을 때 나올 수 있는 게임 상황이면 1을 아니라면 0을 return 하는 solution 함수를 작성해 주세요.

제한사항

• board의 길이 = board[i]의 길이 = 3
  • board의 원소는 모두 "O", "X", "."으로만 이루어져 있습니다.
• board[i][j]는 i + 1행 j + 1열에 해당하는 칸의 상태를 나타냅니다.
  • "."은 빈칸을, "O"와 "X"는 해당 문자로 칸이 표시되어 있다는 의미입니다.

코드

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

int solution(vector<string> board) {
    int onum = 0, xnum = 0;
    for(string s : board){
        for(char c : s){
            if(c == 'O') onum++;
            else if(c == 'X') xnum++;
        }
    }
    if(onum < xnum || onum - xnum > 1) return 0;
    
    bool owin = false, xwin = false;
    for(int i = 0; i < 3; i++){
        if(board[i][0] != '.' && board[i][0] == board[i][1] && board[i][0] == board[i][2]) {
            if(board[i][0] == 'O') owin = true;
            else xwin = true;
        }
        if(board[0][i] != '.' && board[0][i] == board[1][i] && board[0][i] == board[2][i]) {
            if(board[0][i] == 'O') owin = true;
            else xwin = true;
        }
    }
    if(board[0][0] != '.' && board[0][0] == board[1][1] && board[0][0] == board[2][2]){
        if(board[0][0] == 'O') owin = true;
        else xwin = true;
    }
    if(board[2][0] != '.' && board[2][0] == board[1][1] && board[2][0] == board[0][2])  {
        if(board[2][0] == 'O') owin = true;
        else xwin = true;
    }
    
    if(owin){
        if(xwin) return 0;
        else if(onum <= xnum) return 0;
    }
    else if(xwin && onum != xnum) return 0;
    return 1;
}

3x3의 작은 배열이므로 그냥 모든 경우의 수를 구해서 풀어도 된다.

미로 탈출

문제 설명
1 x 1 크기의 칸들로 이루어진 직사각형 격자 형태의 미로에서 탈출하려고 합니다. 각 칸은 통로 또는 벽으로 구성되어 있으며, 벽으로 된 칸은 지나갈 수 없고 통로로 된 칸으로만 이동할 수 있습니다. 통로들 중 한 칸에는 미로를 빠져나가는 문이 있는데, 이 문은 레버를 당겨서만 열 수 있습니다. 레버 또한 통로들 중 한 칸에 있습니다. 따라서, 출발 지점에서 먼저 레버가 있는 칸으로 이동하여 레버를 당긴 후 미로를 빠져나가는 문이 있는 칸으로 이동하면 됩니다. 이때 아직 레버를 당기지 않았더라도 출구가 있는 칸을 지나갈 수 있습니다. 미로에서 한 칸을 이동하는데 1초가 걸린다고 할 때, 최대한 빠르게 미로를 빠져나가는데 걸리는 시간을 구하려 합니다.

미로를 나타낸 문자열 배열 maps가 매개변수로 주어질 때, 미로를 탈출하는데 필요한 최소 시간을 return 하는 solution 함수를 완성해주세요. 만약, 탈출할 수 없다면 -1을 return 해주세요.

제한사항

• 5 ≤ maps의 길이 ≤ 100
  • 5 ≤ maps[i]의 길이 ≤ 100
  • maps[i]는 다음 5개의 문자들로만 이루어져 있습니다.
    • S : 시작 지점
    • E : 출구
    • L : 레버
    • O : 통로
    • X : 벽
  • 시작 지점과 출구, 레버는 항상 다른 곳에 존재하며 한 개씩만 존재합니다.
  • 출구는 레버가 당겨지지 않아도 지나갈 수 있으며, 모든 통로, 출구, 레버, 시작점은 여러 번 지나갈 수 있습니다.

코드

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

vector<string> _maps;
int n, m, sx, sy, lx, ly, ex, ey;
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};

int bfs(int x, int y, int fx, int fy) {
    queue<pair<int, int>> q;
    vector<vector<int>> dis(n, vector<int>(m, -1));
    q.push({x, y});
    dis[x][y] = 0;
    
    while(!q.empty()){
        x = q.front().first;
        y = q.front().second;
        q.pop();
        
        if(x == fx && y == fy) return dis[x][y];
        for(int i = 0; i < 4; i++){
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(dis[nx][ny] != -1 || _maps[nx][ny] == 'X') continue;
            q.push({nx, ny});
            dis[nx][ny] = dis[x][y] + 1;
        }
    }
    return -1;
}

int solution(vector<string> maps) {
    _maps = maps;
    n = maps.size(); m = maps[0].size();
    for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
            if(maps[i][j] == 'S') {
                sx = i; sy = j;
            }
            else if(maps[i][j] == 'E') {
                ex = i; ey = j;
            }
            else if(maps[i][j] == 'L') {
                lx = i; ly = j;
            }
        }
    }
    int move1 = bfs(sx, sy, lx, ly);
    int move2 = bfs(lx, ly, ex, ey);
    if(move1 == -1 || move2 == -1) return -1;
    return move1 + move2;
}

S에서 L까지의 최단 거리 + L에서 E까지의 최단 거리를 구하면 된다.

이모티콘 할인행사

문제 설명
카카오톡에서는 이모티콘을 무제한으로 사용할 수 있는 이모티콘 플러스 서비스 가입자 수를 늘리려고 합니다.
이를 위해 카카오톡에서는 이모티콘 할인 행사를 하는데, 목표는 다음과 같습니다.

1. 이모티콘 플러스 서비스 가입자를 최대한 늘리는 것.
2. 이모티콘 판매액을 최대한 늘리는 것.

1번 목표가 우선이며, 2번 목표가 그 다음입니다.

이모티콘 할인 행사는 다음과 같은 방식으로 진행됩니다.

• n명의 카카오톡 사용자들에게 이모티콘 m개를 할인하여 판매합니다.

• 이모티콘마다 할인율은 다를 수 있으며, 할인율은 10%, 20%, 30%, 40% 중 하나로 설정됩니다.
  카카오톡 사용자들은 다음과 같은 기준을 따라 이모티콘을 사거나, 이모티콘 플러스 서비스에 가입합니다.

• 각 사용자들은 자신의 기준에 따라 일정 비율 이상 할인하는 이모티콘을 모두 구매합니다.

• 각 사용자들은 자신의 기준에 따라 이모티콘 구매 비용의 합이 일정 가격 이상이 된다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

다음은 2명의 카카오톡 사용자와 2개의 이모티콘이 있을때의 예시입니다.

사용자	비율	가격
1	40	10,000
2	25	10,000

이모티콘	가격
1	7,000
2	9,000

1번 사용자는 40%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.
2번 사용자는 25%이상 할인하는 이모티콘을 모두 구매하고, 이모티콘 구매 비용이 10,000원 이상이 되면 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입합니다.

1번 이모티콘의 가격은 7,000원, 2번 이모티콘의 가격은 9,000원입니다.

만약, 2개의 이모티콘을 모두 40%씩 할인한다면, 1번 사용자와 2번 사용자 모두 1,2번 이모티콘을 구매하게 되고, 결과는 다음과 같습니다.

사용자	구매한 이모티콘	이모티콘 구매 비용	이모티콘 플러스 서비스 가입 여부
1	1, 2	9,600	X
2	1, 2	9,600	X

이모티콘 플러스 서비스 가입자는 0명이 늘어나고 이모티콘 판매액은 19,200원이 늘어납니다.

하지만, 1번 이모티콘을 30% 할인하고 2번 이모티콘을 40% 할인한다면 결과는 다음과 같습니다.

사용자	구매한 이모티콘	이모티콘 구매 비용	이모티콘 플러스 서비스 가입 여부
1	2	5,400	X
2	1, 2	10,300	O

2번 사용자는 이모티콘 구매 비용을 10,000원 이상 사용하여 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입하게 됩니다.
따라서, 이모티콘 플러스 서비스 가입자는 1명이 늘어나고 이모티콘 판매액은 5,400원이 늘어나게 됩니다.

카카오톡 사용자 n명의 구매 기준을 담은 2차원 정수 배열 users, 이모티콘 m개의 정가를 담은 1차원 정수 배열 emoticons가 주어집니다. 이때, 행사 목적을 최대한으로 달성했을 때의 이모티콘 플러스 서비스 가입 수와 이모티콘 매출액을 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.

제한사항

• 1 ≤ users의 길이 = n ≤ 100
  • users의 원소는 [비율, 가격]의 형태입니다.
  • users[i]는 i+1번 고객의 구매 기준을 의미합니다.
  • 비율% 이상의 할인이 있는 이모티콘을 모두 구매한다는 의미입니다.
    • 1 ≤ 비율 ≤ 40
  • 가격이상의 돈을 이모티콘 구매에 사용한다면, 이모티콘 구매를 모두 취소하고 이모티콘 플러스 서비스에 가입한다는 의미입니다.
    • 100 ≤ 가격 ≤ 1,000,000
    • 가격은 100의 배수입니다.
• 1 ≤ emoticons의 길이 = m ≤ 7
  • emoticons[i]는 i+1번 이모티콘의 정가를 의미합니다.
  • 100 ≤ emoticons의 원소 ≤ 1,000,000
  • emoticons의 원소는 100의 배수입니다.

코드

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

int n, eplus, price;
vector<int> sale, _emoticons;
vector<vector<int>> _users;
int pc[4] = {10, 20, 30, 40};

void buy(int k) {
    if(k == n) {
        int cnt = 0, emo = 0;
        for(vector<int> v : _users) {
            int now = 0;
            for(int i = 0; i < n; i++){
                if(sale[i] >= v[0]) now += (_emoticons[i] * (100 - sale[i]) / 100);
            }
            if(now >= v[1]) ++cnt;
            else emo += now;
        }
        if(eplus < cnt) {
            eplus = cnt; price = emo;
        }
        else if(eplus == cnt) price = max(price, emo);
        return;
    }
    for(int i = 0; i < 4; i++){
        sale[k] = pc[i];
        buy(k + 1);
    }
    
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    n = emoticons.size();
    _users = users; _emoticons = emoticons;
    sale = vector<int>(n, 0);
    buy(0);
    
    return {eplus, price};
}

이모티콘의 할인률이 4가지, 이모티콘 개수가 7개이므로 모든 이모티콘의 모든 할인률을 계산해서 최댓값을 구해도 4*7가지밖에 없기 때문에 연산량이 그다지 많지 않다.

택배 배달과 수거하기

문제 설명

당신은 일렬로 나열된 n개의 집에 택배를 배달하려 합니다. 배달할 물건은 모두 크기가 같은 재활용 택배 상자에 담아 배달하며, 배달을 다니면서 빈 재활용 택배 상자들을 수거하려 합니다.
배달할 택배들은 모두 재활용 택배 상자에 담겨서 물류창고에 보관되어 있고, i번째 집은 물류창고에서 거리 i만큼 떨어져 있습니다. 또한 i번째 집은 j번째 집과 거리 j - i만큼 떨어져 있습니다. (1 ≤ i ≤ j ≤ n)
트럭에는 재활용 택배 상자를 최대 cap개 실을 수 있습니다. 트럭은 배달할 재활용 택배 상자들을 실어 물류창고에서 출발해 각 집에 배달하면서, 빈 재활용 택배 상자들을 수거해 물류창고에 내립니다. 각 집마다 배달할 재활용 택배 상자의 개수와 수거할 빈 재활용 택배 상자의 개수를 알고 있을 때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 구하려 합니다. 각 집에 배달 및 수거할 때, 원하는 개수만큼 택배를 배달 및 수거할 수 있습니다.

다음은 cap=4 일 때, 최소 거리로 이동하면서 5개의 집에 배달 및 수거하는 과정을 나타낸 예시입니다.

배달 및 수거할 재활용 택배 상자 개수

	집 #1	집 #2	집 #3	집 #4	집 #5
배달	1개	0개	3개	1개	2개
수거	0개	3개	0개	4개	0개

배달 및 수거 과정

	집 #1	집 #2	집 #3	집 #4	집 #5	설명
남은 배달/수거	1/0	0/3	3/0	1/4	2/0	물류창고에서 택배 3개를 트럭에 실어 출발합니다.
남은 배달/수거	1/0	0/3	3/0	0/4	0/0	물류창고에서 5번째 집까지 이동하면서(거리 5) 4번째 집에 택배 1개를 배달하고, 5번째 집에 택배 2개를 배달합니다.
남은 배달/수거	1/0	0/3	3/0	0/0	0/0	5번째 집에서 물류창고까지 이동하면서(거리 5) 4번째 집에서 빈 택배 상자 4개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내리고 택배 4개를 트럭에 싣습니다.
남은 배달/수거	0/0	0/3	0/0	0/0	0/0	물류창고에서 3번째 집까지 이동하면서(거리 3) 1번째 집에 택배 1개를 배달하고, 3번째 집에 택배 3개를 배달합니다.
남은 배달/수거	0/0	0/0	0/0	0/0	0/0	3번째 집에서 물류창고까지 이동하면서(거리 3) 2번째 집에서 빈 택배 상자 3개를 수거한 후, 수거한 빈 택배 상자를 물류창고에 내립니다.

16(=5+5+3+3)의 거리를 이동하면서 모든 배달 및 수거를 마쳤습니다. 같은 거리로 모든 배달 및 수거를 마치는 다른 방법이 있지만, 이보다 짧은 거리로 모든 배달 및 수거를 마치는 방법은 없습니다.

트럭에 실을 수 있는 재활용 택배 상자의 최대 개수를 나타내는 정수 cap, 배달할 집의 개수를 나타내는 정수 n, 각 집에 배달할 재활용 택배 상자의 개수를 담은 1차원 정수 배열 deliveries와 각 집에서 수거할 빈 재활용 택배 상자의 개수를 담은 1차원 정수 배열 pickups가 매개변수로 주어집니다. 이때, 트럭 하나로 모든 배달과 수거를 마치고 물류창고까지 돌아올 수 있는 최소 이동 거리를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ cap ≤ 50
• 1 ≤ n ≤ 100,000
• deliveries의 길이 = pickups의 길이 = n
  • deliveries[i]는 i+1번째 집에 배달할 재활용 택배 상자의 개수를 나타냅니다.
  • pickups[i]는 i+1번째 집에서 수거할 빈 재활용 택배 상자의 개수를 나타냅니다.
  • 0 ≤ deliveries의 원소 ≤ 50
  • 0 ≤ pickups의 원소 ≤ 50
• 트럭의 초기 위치는 물류창고입니다.

코드

테스트 16, 17 시간 초과

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

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    int idx = n - 1, del = 0, pic = 0;
    while(1) {
        int now = 0, box = 0, dis = 0;
        for(int i = n - 1; i >= 0; i--) {
            if(now == cap && box == cap) break;
            if(deliveries[i] > 0 && now < cap) {
                dis = max(dis, i + 1);
                del = i;
                if(deliveries[i] + now <= cap) {
                    now += deliveries[i];
                    deliveries[i] = 0;
                }
                else {
                    deliveries[i] -= (cap - now);
                    now = cap;
                }
            }
            if(pickups[i] > 0 && box < cap) {
                dis = max(dis, i + 1);
                pic = i;
                if(pickups[i] + box <= cap) {
                    box += pickups[i];
                    pickups[i] = 0;
                }
                else {
                    pickups[i] -= (cap - box);
                    box = cap;
                }
            }
        }
        idx = max(del, pic);
        if(dis == 0) break;
        else answer += (dis * 2);
    }
    return answer;
}

n번째 집(idx : n-1)부터 시작하며 배달과 수거를 했다. 아무래도 계속 i = n-1부터 시작하므로 비효율적인 것 같았다.

성공

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

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0, delnum = 0, picnum = 0;
    for(int i = 0; i < n; i++){
        delnum += deliveries[i];
        picnum += pickups[i];
    }
    while(1) {
        int now = 0, box = 0, dis = 0;
        for(int i = idx; i >= 0; i--) {
            if((now == cap || delnum <= 0) && (box == cap || picnum <= 0)) break;
            if(deliveries[i] > 0 && now < cap) {
                dis = max(dis, i + 1);
                if(deliveries[i] + now <= cap) {
                    now += deliveries[i];
                    deliveries[i] = 0;
                }
                else {
                    deliveries[i] -= (cap - now);
                    now = cap;
                }
            }
            if(pickups[i] > 0 && box < cap) {
                dis = max(dis, i + 1);
                if(pickups[i] + box <= cap) {
                    box += pickups[i];
                    pickups[i] = 0;
                }
                else {
                    pickups[i] -= (cap - box);
                    box = cap;
                }
            }
        }
        idx = max(del, pic);
        if(dis == 0) break;
        else answer += (dis * 2);
        delnum -= cap; picnum -= cap;
    }
    return answer;
}

처음에는 idx 변수를 이용해 시작하는 집만 변경하게 했다. 배달과 수거 중 해야하는 일이 남은(?) 집의 인덱스가 더 큰 곳을 저장하게 해서 해당 인덱스부터 다시 시작하게 했으나.. 17번에서 또 시간초과.

작성한 코드에서는 now(배달한 상자 수)와 box(수거한 상자 수)가 cap이 되어야만 for문에서 탈출하므로, 둘 중 하나의 작업이 모두 끝난 상태에서 다른 작업을 하는 경우 i = 0이 될 때까지 for문을 탈출할 수 없다. 이것 때문에 시간 초과가 발생하는 것으로 판단해서 남은 배달 수, 남은 수거 수를 나타내는 변수를 만들어 관리했다.