99코딩

• i점에서 라이언이 어피치보다 1발 더 맞춰야 라이언이 득점
• 2발 더 맞춰도 얻는 점수는 같기에 어피치보다 2발 이상 맞추는건 낭비
• 가장 큰 점수 차로 이기는게 여러가지면, 가장 낮은 점수를 더 많이 맞춘 경우를 리턴 > 각 점수마다 위를 반복한 후 남은 화살을 전부 0점에서 소모
• 위를 조건으로 화살 명중 조합을 만들고 각 조합마다 점수를 계산해서 점수차가 가장 큰 경우와 해당 경우가 2개 이상일 시 0점에서 소모된 화살이 더 많은 경우를 리턴
• 점수가 어피치보다 낮으면 -1 리턴

#include <string>
#include <vector>

using namespace std;

// 완전탐색 필요 > dfs 사용

int bestDiff = -1, RyanScore = 0, ApeachScore = 0;
vector<int> score, ryan, apeach, ryanBest;

void checkCondition() {
    int diff = RyanScore - ApeachScore;
    
    // ryan의 점수에서 apeach의 점수를 뺀 값이 0이하면 ryan이 이긴 것이 아님
    if(diff <= 0) return;
    // ryan이 이겼다면
    else {
        // 현재 최고점하고 diff가 같다면
        if(bestDiff == diff) {
            // 가장 낮은 점수를 더 많이 맞힌 경우 구하기
            // 가장 낮은 점수를 맞춘 수가 동일하다면 그 다음으로 낮은 점수로 넘어가야함
            for(int i = 10; i >= 0; i--) {
                // ryan이 0이 아니고 ryanBest가 0인 경우
                if(ryan[i] != 0 && ryanBest[i] == 0) {
                    ryanBest = ryan;
                    break;
                }
                // ryan이 0이고 ryanBest는 0이 아닌 경우
                else if(ryan[i] == 0 && ryanBest[i] != 0)
                    break;
                // 둘의 값이 0이 아니면 비교 필요
                else if(ryan[i] != 0 && ryanBest[i] != 0) {
                    // 둘의 값이 다르면
                    if(ryan[i] != ryanBest[i]) {
                        // ryan이 ryanResult보다 크면
                        if(ryan[i] > ryanBest[i]) {
                            // 점수차는 같으나 배열 갱신 필요
                            ryanBest = ryan;
                            break;
                        }
                    }
                }
            }
        }
        // 현재 최고점보다 ryanScore가 크거나 갱신된 적이 없다면
        else if(diff > bestDiff || bestDiff == -1) {
            // 갱신
            bestDiff = diff;
            ryanBest = ryan;
        }
    }
}

// 점수 계산
void calcScore() {
    int ryanScore = 0;
    int apeachScore = 0;
    
    for(int i = 0; i < 11; i++) {
        // i 배점에서 ryan과 apeach가 맞힌 개수가 동일하면
        if(ryan[i] == apeach[i]) {
            // ryan과 apeach 둘 다 i 점을 맞추지 않았을 때
            if(ryan[i] == 0 && apeach[i] == 0)
                continue;
            else
                apeachScore += 10 - i;
        }
        // 맞힌 개수가 동일하지 않을 때
        else {
            // 라이언이 어피치보다 많이 맞췄으면 라이언 점수 증가 
            if(ryan[i] > apeach[i])
                ryanScore += 10 - i;
            // 아니면 어피치 점수 증가
            else
                apeachScore += 10 - i;
        }
    }
    
    // 라이언 점수
    RyanScore = ryanScore;
    
    // 어피치 점수
    ApeachScore = apeachScore;
}

void dfs(int cnt, int i, int n) {
    // 화살을 전부 사용했으면
    if(cnt == n) {
        // 계산
        calcScore();
        
        // 조건 체크
        checkCondition();
        return;
    }
    
    int remain = n - cnt;
    
    // 가장 큰 점수 차이로 우승하는 방법이 여러가지면, 가장 낮은 점수를 더 많이 맞춰야함
    // 2번째 조건을 위해 i == 10에서 남은 화살이 있으면 전부 소모해야함
    if(i == 10) {
        ryan[i] = remain;
        dfs(cnt + remain, i + 1, n);
        ryan[i] = 0;
    }
    // i == 10이 아닐 때
    else {
        // 남은 화살 수가 apeach[i]보다 크거나 같으면
        if(apeach[i] + 1 <= remain) {
            // apeach[i] + 1을 ryan[i]에 삽입
            ryan[i] = apeach[i] + 1;
            dfs(cnt + ryan[i], i + 1, n);
            ryan[i] = 0;
        }
        
        dfs(cnt, i + 1, n);
    }
}

vector<int> solution(int n, vector<int> info) {
    score.resize(2, 0);
    ryan.resize(11, 0);
    
    apeach = info;
    
    dfs(0, 0, n);
    
    // bestDiff가 갱신된적 없다면 이기는 경우가 없음 > -1 리턴
    if(bestDiff == -1) ryanBest.push_back(-1);
    
    return ryanBest;
}

• 일단 dfs를 통해 각 이모티콘들의 할인 조합을 만들어주기로 함
• 할인율 4종류에 이모티콘은 최대 7종류라 dfs 자체는 최대 28번 수행이라 시간 초과는 없을거라 예상
• 이후 조합이 다 만들어지면 매출액과 플러스 가입자 수를 구함
• 조건 중 플러스 가입자 수 증가가 1순위, 매출액 최대화가 2순위이므로 플러스 가입자 수가 더 많은 조합의 가입자 수와 매출액을 저장하고 가입자 수가 동일하다면 매출액을 비교해서 저장

나름 간단한 완전탐색 문제였다.

#include <string>
#include <vector>

using namespace std;

// 할인율 배열
int discount[4] = {10, 20, 30, 40};

void dfs(int cnt, int size, vector<vector<int>> users, vector<int> emoticons, 
         vector<int>& answer, vector<pair<int, int>>& prices) {
    // 모든 이모티콘에 할인 적용이 완료되었을 때
    if(cnt == size) {
        // 플러스 가입자 수, 매출액
        int plus = 0, total = 0;
        
        // 각 사용자마다
        for(int i = 0;i < users.size(); i++)
        {
            int tmp = 0;
            
            for(int j = 0;j < size; j++)
                // 할인율이 마음에 들면
                if (users[i][0] <= prices[j].second) tmp += prices[j].first;
            // 소지금보다 구매에 많이 사용한다면 플러스 이용자
            if(tmp >= users[i][1]) plus++;
            else total += tmp;
        }
        
        // 가입자 수가 더 많을 때 << 1번 목표
        if (plus > answer[0])
        {
            answer[0] = plus;
            answer[1] = total;
        }
        // 가입자 수가 동일하다면 판매액이 더 클 때 << 2번 목표
        else if(plus == answer[0] && total >= answer[1]) answer[1] = total;
        
        return ;
    }
    
    // 이모티콘 할인 조합 만들기
    for(int i = 0; i < 4; i++) {
        prices[cnt].first = emoticons[cnt] * (100 - discount[i]) / 100;
        prices[cnt].second = discount[i];
        dfs(cnt + 1, size, users, emoticons, answer, prices);
    }
}

vector<int> solution(vector<vector<int>> users, vector<int> emoticons) {
    vector<int> answer(2, 0);
    // {할인가, 할인율} 쌍
    vector<pair<int, int>> prices(7, {0, 0});
    
    dfs(0, emoticons.size(), users, emoticons, answer, prices);
    
    return answer;
}

• 직선 n개 중에서 2개씩 뽑아서 해당 두 직선의 교점을 구해야함
• 무수히 많은 교점이 생기는 직선 쌍은 주어지지 않음 
• 모든 직선 쌍은 교점이 유일하게 존재하거나 평행함
• 문제 아래의 참고 사항에서 두 직선이 평행한지와 두 직선의 교점을 구하는 방법이 나와있으므로 참고하면 됨
• 모든 직선쌍의 교점을 구한 뒤 해당 영역을 그리기 위해 가장 작은 x, y 좌표와 가장 큰 x, y 좌표를 구해야함
• 이후 maxX - minX, maxY - minY가 그릴 영역의 가로, 세로가 됨
• 영역을 그린 뒤 그래프의 좌표와 그린 영역의 좌표가 다른 것을 감안해 좌표이동을 하여 '*'을 해당 좌표에 삽입

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

vector<string> solution(vector<vector<int>> line) {
    vector<string> answer;
    vector<pair<int, int>> coor;
    // minX, maxX, minY, maxY 초기화
    int minX = INT32_MAX, maxX = INT32_MIN, minY = INT32_MAX, maxY = INT32_MIN;
    
    for(int i = 0; i < line.size(); i++) {
        for(int j = i + 1; j < line.size(); j++) {
            
            // 이 값이 0이면 두 직선은 평행
            int isParallel = line[i][0] * line[j][1] - line[i][1] * line[j][0];
            
            // 0이 아니면 교점이 존재
            if(isParallel) {
                long long x = (1LL * line[i][1] * line[j][2] - 1LL * line[i][2] * line[j][1]);
                long long y = (1LL * line[i][2] * line[j][0] - 1LL * line[i][0] * line[j][2]);
                
                // 이 중 정수로만 표현되는 좌표를 저장    
                if(x % isParallel == 0 && y % isParallel == 0) coor.push_back({x / isParallel, y / isParallel});
            }
        }
    }
    
    // 정렬 후 중복되는 좌표 제거
    sort(coor.begin(), coor.end());
    coor.erase(unique(coor.begin(), coor.end()), coor.end());
    
    // minX, maxX, minY, maxY를 구함
    for(int i = 0; i < coor.size(); i++) {
        minX = min(minX, coor[i].first);
        maxX = max(maxX, coor[i].first);
        minY = min(minY, coor[i].second);
        maxY = max(maxY, coor[i].second);
    }
    
    // 각각 영역의 가로, 세로
    int x = maxX - minX, y = maxY - minY;
    
    // 해당 영역의 크기만큼 answer를 '.'로 초기화
    for(int i = 0; i <= y; i++) {
        string board(x + 1, '.');
        answer.push_back(board);
    }
    
    // 좌표이동 후 '*'를 삽입
    for(int i = 0; i < coor.size(); i++) 
        answer[maxY - coor[i].second][coor[i].first - minX] = '*';
    
    return answer;
}

• 각 칸의 숫자는 해당 칸에서 최대 며칠 머물 수 있는지 나타냄
• 이어진 땅들은 하나의 무인도
• X는 갈 수 없음

> bfs를 이용한 풀이

#include <string>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> answer;

char board[101][101] = {'0'};
bool check[101][101] = {false};

int dx[4] = {1, 0 , -1, 0};
int dy[4] = {0, -1, 0 , 1};

void bfs(int posX, int posY, int width, int height) {
    queue<pair<int, int>> q;
    q.push({posX, posY});
    check[posX][posY] = true;
    
    int sum = 0;
    
    while(!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;

        sum += board[x][y] - '0';
        
        q.pop();
        
        for(int i = 0; i < 4; i++) {
            int curX = x + dx[i];
            int curY = y + dy[i];
            
            if(curX < 0 || curX >= width || curY < 0 || curY >= height || check[curX][curY] || board[curX][curY] == 'X') continue;
            
            check[curX][curY] = true;
            q.push({curX,curY});
        }
    }
    
    answer.push_back(sum);
}

vector<int> solution(vector<string> maps) {
    int width = maps.size();
    int height = maps[0].size();
    
    for(int i = 0; i < width; i++)
        for(int j = 0; j < height; j++)
            board[i][j] = maps[i][j];
    
    for(int i = 0; i < width; i++) {
        for(int j = 0; j < height; j++) {
            if(!check[i][j] && maps[i][j] != 'X')
                bfs(i, j , width, height);
        }
    }
    
    sort(answer.begin(), answer.end());
    
    if(answer.empty()) {
        answer.push_back(-1);
        return answer;
    }
    else
        return answer;
}