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;
}

info와, query를 잘라 각각 users와 conditions에 담은 다음

user마다 조건을 체크하면 되지 않을까?

#include <string>
#include <vector>
#include <sstream>

using namespace std;

vector<vector<string>> users;
vector<vector<string>> conditions;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    
    // info 문자열 분리
    for(int i = 0; i < info.size(); i++) {
        istringstream iss(info[i]);
        string token;
        vector<string> tokens;
        
        while (getline(iss, token, ' '))
            tokens.push_back(token);
        
        users.push_back(tokens);
    }
    
    // query 문자열 분리
    for(int i = 0; i < query.size(); i++) {
        istringstream iss(query[i]);
        string token;
        vector<string> tokens;
        
        while (getline(iss, token, ' ')) {
            if (token != "and") {
                tokens.push_back(token);
            }
        }
        
        condition.push_back(token);
    }
    
    // 각 조건마다 조건을 충족하는 유저의 수를 확인
    for(int i = 0; i < conditions.size(); i++) {
        // 이거 최악 50000 x 100000이면 시간 초과날거 같은데?
    }
    
    return answer;
}

작성하다가 중간에 딱봐도 시간초과 날 거 같아서 갈아치웠다

• 그래서 떠오른게 map을 이용해서 특정 조건을 key로 가지는 경우 해당 맵의 value에 그 인원의 점수를 추가 한 뒤
  이후 query를 돌며 각 조건마다 value 벡터에 들어있는 점수가 X점 이상인지 체크하도록 하는 것
• 여기서 query의 조건이 -면 해당 조건을 고려하지 않는 것이므로 어느 문자열이 들어가도 상관없기 때문에
  예를 들어 info의 조건이 java backend junior pizza라면 각 조건들이 -가 될 수 있는 것도 고려해야함

#include <string>
#include <vector>
#include <sstream>
#include <unordered_map>

using namespace std;

unordered_map<string, vector<int>> m;

vector<int> solution(vector<string> info, vector<string> query) {
    vector<int> answer;
    string s[4], score = "";
    
    // info 문자열을 분리
    for(int i = 0; i < info.size(); i++) {
        istringstream iss(info[i]);
        iss >> s[0] >> s[1] >> s[2] >> s[3] >> score;
        
        // 분리된 문자열을 key로 가지는 value 배열에 점수 추가
        // 단 각 조건마다 -이 될 때를 문자열을 key로 가지는 value 배열에도 점수 추가해주어야함
        // 4개의 조건이 각각 info의 조건 또는 -가 될 수 있으므로 점수를 추가해주어야하는 key는 총 16가지
        for(int j = 0; j < 16; j++) {
            string key = "";
            int num = j;
            
            // num % 2 == 0은 -가 되는 경우
            // 0000, 0001, 0010, 0011...
            // 비트마스크를 이용해 조합을 만들어도 될 듯
            for(int k = 0; k <= 3; k++) {
                if(num % 2 == 0)
                    key += "-";
                else
                    key += s[k];
                
                num /= 2;
            }
            
            // unordered_map에 삽입
            m[key].push_back(stoi(score));
        }
    }
    
    // key값의 value에 조건을 충족하는 인원이 몇 명인지 체크
    for(int i = 0; i < query.size(); i++) {
        // 조건을 충족하는 인원 수
        int cnt = 0;
        
        // 조건 문자열 자르기, and 무시 필요
        istringstream iss(query[i]);
        iss >> s[0] >> score >> s[1] >> score >> s[2] >> score >> s[3] >> score;
        
        // key 생성
        string key = s[0] + s[1] + s[2] + s[3];
        // key에 해당하는 value 배열 받아오기
        vector<int> scores = m[key];
        
        // 점수 조건 
        int con = stoi(score);
        
        // scores 배열에서 조건을 충족하는지 체크
        for(int j = 0; j < scores.size(); j++)
            // 충족하면 ++
            if(scores[j] >= con) 
                cnt++;
        
        // 조건을 충족하는 인원 수 저장
        answer.push_back(cnt);
    }
    
    return answer;
}

• 배달/수거해야 하는 물건이 i번째에 하나라도 있다면 i까지는 가야함
• 한 싸이클마다 cap만큼의 배달/수거가 가능
• 싸이클 후 i에 택배가 남아있다면 다시 i로 가야함
• 매 싸이클마다 가장 멀리있는 집부터 해결해야함

탐욕법까지는 떠올렸으나 구현 단계에서 시간이 꽤 걸렸다.

#include <string>
#include <vector>
#include <stack>

using namespace std;

long long solution(int cap, int n, vector<int> deliveries, vector<int> pickups) {
    long long answer = 0;
    
    stack<int> deliver, pickup;
    
    // 가까운 곳에서부터 i + 1의 거리에 위치한 집에 배달/수거해야 하는 물품 수만큼 스택에 해당 집의 거리를 삽입
    // 각각 스택의 top에는 가장 먼 거리가 저장
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < deliveries[i]; j++) 
            deliver.push(i + 1);
        for(int j = 0; j < pickups[i]; j++)
            pickup.push(i + 1);
    }
    
    // deliver 또는 pickup 스택이 비어있지 않다면 배달/수거 필요
    while(!deliver.empty() || !pickup.empty()) {
        int distDeliver = 0, distPickup = 0;
        
        // 한 번 출발 시 cap만큼 배달과 수거가 가능
        for(int i = 0; i < cap; i++) {
            // deliver 스택이 비어있지 않다면
            if(!deliver.empty()) {
                if(i == 0) distDeliver = deliver.top();
                deliver.pop();   
            }
            
            // pickup 스택이 비어있지 않다면
            if(!pickup.empty()) {
                if(i == 0) distPickup = pickup.top();
                pickup.pop();
            }
        }
        
        // 한 번 출발 시 둘 중 더 먼 거리까지 왕복하는 것이 한 싸이클이기 때문에 더 큰 값 x 2를 answer에 더함
        answer += max(distDeliver, distPickup) * 2;
    }
    
    return answer;
}

일단 여기서 틱택토가 정상적으로 진행되지 않는 경우는

• 턴이 제대로 주어지지 않음(cntX > cntO or cntO > cntX + 1) 즉, 한 쪽이 한 번 이상 더 많이 둠
• O가 승리했는데 cntO - cntX가 1이 아님
• X가 승리했는데 cntO == cntX가 아님
• 둘 다 승리함 < 이거를 고려안하고 작성하다가 중간에 whoWin 메서드를 고침

이렇게 4가지다

위 조건을 모두 통과하면 정상적으로 틱택토가 진행된 것

#include <string>
#include <vector>

using namespace std;

// 누가 이겼는가
bool whoWin(vector<string> board, char target) {
    // 가로 세로 체크
    for(int i = 0; i < 3; i++) {
        if(board[i][0] == target && board[i][0] == board[i][1] && board[i][1] == board[i][2])
            return true;
        
        if(board[0][i] == target && board[0][i] == board[1][i] && board[1][i] == board[2][i])
            return true;
    }
    
    // 대각선 체크
    if(board[0][0] == target && board[0][0] == board[1][1] && board[1][1] == board[2][2])
        return true;
    
    if(board[2][0] == target && board[2][0] == board[1][1] && board[1][1] == board[0][2])
        return true;
    
    return false;
}

int solution(vector<string> board) {
    int cntO = 0, cntX = 0;
    
    // O와 X 수 세기
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) {
            if(board[i][j] == 'O') cntO++;
            if(board[i][j] == 'X') cntX++;
        }
    
    // 공평한 턴이 주어졌는가
    if((cntO < cntX) || (cntO > cntX + 1)) return 0;
    // O가 이겼는데 X가 수를 뒀는가
    if(whoWin(board, 'O') && cntO - cntX != 1) return 0;
    // X가 이겼는데 O가 수를 뒀는가
    if(whoWin(board, 'X') && cntO - cntX != 0) return 0;
    // O, X 둘 다 이겼는가
    if(whoWin(board, 'O') && whoWin(board, 'X')) return 0;
    
    return 1;
}

• 프렌즈들이 줄을 서는 모든 경우의 수 중 data의 조건들을 충족하는 것들을 찾아야 함
• 순열을 통해 모든 경우의 수를 만들고 각 경우의 수마다 조건을 충족하는지 체크
• 순열 사용 시 사용할 컨테이너는 오름차순으로 정렬되어 있어야함

옛날 문제라 그런진 모르겠지만 정답률에 비해 난이도가 쉬웠던 문제

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

using namespace std;

bool conditionCheck(char oper, int nowDist, int conDist) {
    // 주어진 조건이 = 일 때 
    if(oper == '=') return nowDist == conDist;
    // 주어진 연산자가 > 일 때
    else if(oper == '>') return nowDist > conDist;
    // 주어진 연산자가 < 일 때
    else return nowDist < conDist;
}

// 전역 변수를 정의할 경우 함수 내에 초기화 코드를 꼭 작성해주세요.
int solution(int n, vector<string> data) {
    int answer = 0;
    
    string friends = "ACFJMNRT";
    
    sort(friends.begin(), friends.end());
    
    do {
        bool isCorrect = true;
        
        for(int i = 0; i < data.size(); i++) {
            // 조건을 제시한 프렌즈
            int idx1 = friends.find(data[i][0]);
            // 상대방
            int idx2 = friends.find(data[i][2]);
            // 제시자와 상대방 간의 현재 거리
            int nowDist = abs(idx1 - idx2) - 1;
            // 조건 거리
            int conDist = data[i][4] - '0';
            
            if(conditionCheck(data[i][3], nowDist, conDist)) continue;
            else { 
                isCorrect = false;
                break;   
            }
        }
        
        // 조건 만족하면 answer++
        if(isCorrect) answer++;
        
    } while(next_permutation(friends.begin(), friends.end())); // 순열
    
    return answer;
}

• 무조건 한 번 부딪혀야하고 진행 방향은 항상 입사각과 반사각이 동일
• 두 좌표를 부딪히는 부분 기준으로 펼쳐셔 피타고라스 법칙으로 직선 거리를 구해보았다

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

using namespace std;

vector<int> solution(int m, int n, int startX, int startY, vector<vector<int>> balls) {
    vector<int> answer;
    
    for(int i = 0; i < balls.size(); i++) {
        int distance = INT32_MAX;
        int targetX = balls[i][0];
        int targetY = balls[i][1];
        
        // 상
        if(startX != targetX || startY <= targetY)
            distance = min(distance, (int)(pow(startX - targetX, 2) + pow(startY + targetY, 2)));
        // 하
        if(startX != targetX || startY >= targetY)
            distance = min(distance, (int)(pow(startX - targetX, 2) + pow(startY - 2 * n + targetY, 2)));
        // 좌
        if(startX >= targetX || startY != targetY)
            distance = min(distance, (int)(pow(startX - 2 * m + targetX, 2) + pow(startY - targetY, 2)));
        // 우
        if(startX <= targetX || startY != targetY)
            distance = min(distance, (int)(pow(startX + targetX, 2) + pow(startY - targetY, 2)));
        
        answer.push_back(distance);
    }
    
    return answer;
}

#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

long long solution(int r1, int r2) {
    long long answer = 0;

    // 축을 제외한 한 사분면에 존재할 수 있는 정수 좌표의 수 구하기
    for (int i = 1; i < r2; ++i) {
        int bigRound = 0;
        int smallRound = 0;

        // 큰 원 내부에서 x좌표가 i일 때 존재할 수 있는 정수 좌표의 수
        bigRound = floor(sqrt(pow(r2, 2) - pow(i, 2)));
        
        if(i < r1)
            // 작은 원 내부에서 x좌표가 i일 때 존재할 수 있는 정수 좌표의 수
            smallRound = ceil(sqrt(pow(r1, 2) - pow(i, 2)));
        else
            smallRound = 1;
              
        answer += (bigRound - smallRound + 1);
    }

    // 4 x (한 사분면의 좌표 수 + 한 축 위에 존재할 수 있는 큰 원과 작은 원 사이의 좌표 수(= r2 -r1 + 1))
    return 4 * (answer + r2 - r1 + 1);
}