오늘의 문제
주사위 고르기

산 모양 타일링

[PCCP 기출문제] 1번 / 붕대 감기

카카오 4번은 아직.. 못 풀었다...

주사위 고르기

문제 설명
A와 B가 n개의 주사위를 가지고 승부를 합니다. 주사위의 6개 면에 각각 하나의 수가 쓰여 있으며, 주사위를 던졌을 때 각 면이 나올 확률은 동일합니다. 각 주사위는 1 ~ n의 번호를 가지고 있으며, 주사위에 쓰인 수의 구성은 모두 다릅니다.

A가 먼저 n / 2개의 주사위를 가져가면 B가 남은 n / 2개의 주사위를 가져갑니다. 각각 가져간 주사위를 모두 굴린 뒤, 나온 수들을 모두 합해 점수를 계산합니다. 점수가 더 큰 쪽이 승리하며, 점수가 같다면 무승부입니다.

A는 자신이 승리할 확률이 가장 높아지도록 주사위를 가져가려 합니다.

다음은 n = 4인 예시입니다.

주사위	구성
#1	[1, 2, 3, 4, 5, 6]
#2	[3, 3, 3, 3, 4, 4]
#3	[1, 3, 3, 4, 4, 4]
#4	[1, 1, 4, 4, 5, 5]

• 예를 들어 A가 주사위 #1, #2를 가져간 뒤 6, 3을 굴리고, B가 주사위 #3, #4를 가져간 뒤 4, 1을 굴린다면 A의 승리입니다. (6 + 3 > 4 + 1)

A가 가져가는 주사위 조합에 따라, 주사위를 굴린 1296가지 경우의 승패 결과를 세어보면 아래 표와 같습니다.

A의 주사위	승	무	패
#1, #2	596	196	504
#1, #3	560	176	560
#1, #4	616	184	496
#2, #3	496	184	616
#2, #4	560	176	560
#3, #4	504	196	596

A가 승리할 확률이 가장 높아지기 위해선 주사위 #1, #4를 가져가야 합니다.

주사위에 쓰인 수의 구성을 담은 2차원 정수 배열 dice가 매개변수로 주어집니다. 이때, 자신이 승리할 확률이 가장 높아지기 위해 A가 골라야 하는 주사위 번호를 오름차순으로 1차원 정수 배열에 담아 return 하도록 solution 함수를 완성해 주세요. 승리할 확률이 가장 높은 주사위 조합이 유일한 경우만 주어집니다.

제한사항

• 2 ≤ dice의 길이 = n ≤ 10
  - n은 2의 배수입니다.
  - dice[i]는 i+1번 주사위에 쓰인 6개의 수를 담고 있습니다.
  - dice[i]의 길이 = 6
  - 1 ≤ dice[i]의 원소 ≤ 100
  

코드

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

vector<vector<int>> ddice;
int n;

// 현재 팀에 속한 주사위를 굴렸을 때 나올 수 있는 합의 조합 구하기
vector<int> roll(vector<int> team){
    vector<int> num(ddice[team[0]].begin(), ddice[team[0]].end());
    int now = ddice[team[0]].size();
    for(int t = 1; t < team.size(); t++){
        for(int i : ddice[team[t]]) {
            for(int j = 0; j < now; j++){
                num.emplace_back(num[j] + i);
            }
        }
        num.erase(num.begin(), num.begin() + now);
        now = num.size();
    }
    return num;
}

// 현재 선택된 팀의 승리 개수 비교(1&2, 3&4이면 1&2의 승리 개수를 구함)
int result(vector<int> t1, vector<int> t2){
    int win = 0;
    vector<int> t1_num = roll(t1);
    vector<int> t2_num = roll(t2);
    
    for(int n1 : t1_num){
        for(int n2 : t2_num){
            if(n1 > n2) ++win;
        }
    }
    return win;
}

vector<int> solution(vector<vector<int>> dice) {
    n = dice.size();
    ddice = dice;
    
    vector<int> arr(n, 1);
    fill(arr.begin(), arr.begin() + n / 2, 0);
    int arrs = pow(pow(2, n / 2), 2);
    int max_pct = 0, total = pow(6, n/2);
    vector<int> team;
    
    do {
        if(--arrs <= 0) break;
        vector<int> t1, t2;
        for(int i = 0; i < n; i++){
            if(arr[i]) t1.emplace_back(i);
            else t2.emplace_back(i);
        }
        int rst = result(t1, t2);
        
        if(max_pct < rst) {
            max_pct = rst;
            team = t1;
        }
        if(max_pct < (total - rst)){
            max_pct = total - rst;
            team = t2;
        }
    } while(next_permutation(arr.begin(), arr.end()));
    
    for(int i = 0; i < team.size(); i++) team[i]++;

    return team;
}

산 모양 타일링

문제 설명
한 변의 길이가 1인 정삼각형 2n+1개를 이어붙여 윗변의 길이가 n, 아랫변의 길이가 n+1인 사다리꼴을 만들 수 있습니다. 이때 사다리꼴의 윗변과 변을 공유하는 n개의 정삼각형 중 일부의 위쪽에 같은 크기의 정삼각형을 붙여 새로운 모양을 만들었습니다. 예를 들어 n이 4이고, 1번째, 2번째, 4번째 정삼각형 위에 정삼각형을 붙인 모양은 다음과 같습니다.

이렇게 만든 모양을 정삼각형 타일 또는 정삼각형 2개를 이어 붙인 마름모 타일로 빈 곳이 없도록 채우려고 합니다. 정삼각형 타일과 마름모 타일은 돌려서 사용할 수 있습니다.

타일을 놓을 때 다른 타일과 겹치거나 모양을 벗어나게 놓을 수는 없습니다. 위의 예시 모양을 채우는 방법 중 일부는 다음과 같습니다.

사다리꼴의 윗변의 길이를 나타내는 정수 n과 사다리꼴 윗변에 붙인 정삼각형을 나타내는 1차원 정수 배열 tops가 매개변수로 주어집니다. 이때 문제 설명에 따라 만든 모양을 정삼각형 또는 마름모 타일로 빈 곳이 없도록 채우는 경우의 수를 10007로 나눈 나머지를 return 하도록 solution 함수를 완성해 주세요.

제한사항

• 1 ≤ n ≤ 100,000
• tops의 길이 = n
  - tops[i]는 사다리꼴의 윗변과 변을 공유하는 i+1번째 정삼각형의 위쪽에 정삼각형을 붙이는 경우 1, 붙이지 않는 경우 0입니다.
  

코드

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

vector<vector<int>> arr;	// 산 모양 타일을 2차원 배열로 저장
int dp[200005], N;

int dfs(int k) {
    if(k == N) return 1;
    if(dp[k] != 0) return dp[k] % 10007;
    
    if(arr[0][k]) {
        arr[0][k] = 0; arr[1][k] = 0;
        dp[k] += dfs(k+1);
        arr[0][k] = 1; arr[1][k] = 1;
    }
    if(k <= N - 2){
        arr[1][k] = 0; arr[1][k+1] = 0;
        dp[k] += dfs(k+2);
        arr[1][k] = 1; arr[1][k+1] = 1;
    }
    arr[1][k] = 0;
    dp[k] += dfs(k+1);
    arr[1][k] = 0;
    return dp[k] % 10007;
}

int solution(int n, vector<int> tops) {
    N = 2 * n + 1;
    arr = vector<vector<int>>(2, vector<int>(N, 1));
    fill(arr[0].begin(), arr[0].end(), 0);
    for(int i = 0; i < tops.size(); i++){
        if(tops[i]) arr[0][i * 2 + 1] = 1;
    }
    return dfs(0) ;
}

산 모양 타일을 2차원 배열에 저장했다. 0행은 위에 붙은 정삼각형, 1행은 아래의 정삼각형과 역삼각형을 나타내고, 1행의 홀수 열은 정삼각형, 짝수 열은 역삼각형이다. (배열은 어떻게 하든 딱히 중요하지 않을 것 같다)

dfs만으로 풀기에는 반복되는 연산이 많을 것 같아서 DP를 같이 이용했다. dp[k]에는 arr의 k행부터 N-1행까지에 타일을 놓을 수 있는 가짓수를 저장한다.

(k번째 역삼각형의 위에 삼각형이 놓여 있는 경우) 세로로 긴 마름모를 놓는 경우 + 가로로 마름모를 놓는 경우(배열로 바꿨기 때문에 모양은 무시하고 k, k+1에 놓으면 된다) + 그냥 삼각형으로 남겨 두는 경우를 더해서 계산하면 된다.

생각보다 쉽게 풀었다.

[PCCP 기출문제] 1번 / 붕대 감기

문제 설명
어떤 게임에는 붕대 감기라는 기술이 있습니다.

붕대 감기는 t초 동안 붕대를 감으면서 1초마다 x만큼의 체력을 회복합니다. t초 연속으로 붕대를 감는 데 성공한다면 y만큼의 체력을 추가로 회복합니다. 게임 캐릭터에는 최대 체력이 존재해 현재 체력이 최대 체력보다 커지는 것은 불가능합니다.

기술을 쓰는 도중 몬스터에게 공격을 당하면 기술이 취소되고, 공격을 당하는 순간에는 체력을 회복할 수 없습니다. 몬스터에게 공격당해 기술이 취소당하거나 기술이 끝나면 그 즉시 붕대 감기를 다시 사용하며, 연속 성공 시간이 0으로 초기화됩니다.

몬스터의 공격을 받으면 정해진 피해량만큼 현재 체력이 줄어듭니다. 이때, 현재 체력이 0 이하가 되면 캐릭터가 죽으며 더 이상 체력을 회복할 수 없습니다.

당신은 붕대감기 기술의 정보, 캐릭터가 가진 최대 체력과 몬스터의 공격 패턴이 주어질 때 캐릭터가 끝까지 생존할 수 있는지 궁금합니다.

붕대 감기 기술의 시전 시간, 1초당 회복량, 추가 회복량을 담은 1차원 정수 배열 bandage와 최대 체력을 의미하는 정수 health, 몬스터의 공격 시간과 피해량을 담은 2차원 정수 배열 attacks가 매개변수로 주어집니다. 모든 공격이 끝난 직후 남은 체력을 return 하도록 solution 함수를 완성해 주세요. 만약 몬스터의 공격을 받고 캐릭터의 체력이 0 이하가 되어 죽는다면 -1을 return 해주세요.

제한사항

• bandage는 [시전 시간, 초당 회복량, 추가 회복량] 형태의 길이가 3인 정수 배열입니다.
  - 1 ≤ 시전 시간 = t ≤ 50
  - 1 ≤ 초당 회복량 = x ≤ 100
  - 1 ≤ 추가 회복량 = y ≤ 100
• 1 ≤ health ≤ 1,000
• 1 ≤ attacks의 길이 ≤ 100
  - attacks[i]는 [공격 시간, 피해량] 형태의 길이가 2인 정수 배열입니다.
  - attacks는공격 시간을 기준으로 오름차순 정렬된 상태입니다.
  - attacks의 공격 시간은 모두 다릅니다.
  - 1 ≤ 공격 시간 ≤ 1,000
  - 1 ≤ 피해량 ≤ 100

코드

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

int solution(vector<int> bandage, int health, vector<vector<int>> attacks) {
    int n = 0, att = 0, max_h = health;
    for(int t = attacks[0][0]; t <= attacks[attacks.size() - 1][0]; t++) {
        if(t == attacks[att][0]){
            health -= attacks[att][1];
            ++att; n = 0;
            if(health < 0) return -1;
            if(att == attacks.size()) break;
            continue;
        }
        health = min(health + bandage[1], max_h);
        ++n;
        if(n == bandage[0]) {
            health = min(health + bandage[2], max_h);
            n = 0;
        }
    }
    return (health > 0 ? health : -1);
}

시간이 흘러감에 따라 조건에 맞춰 health를 증감하기만 하면 되는 문제이다.