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

문제

풀이

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int n, cnt1, cnt2; //cnt1 = 단지 수, cnt2 = 단지 내 집의 수
string area[25];
vector<int> v;
bool isVisited[25][25];

int dirX[] = { 0, 1, 0, -1 };
int dirY[] = { 1, 0, -1, 0 };

void dfs(int y, int x) {
	isVisited[y][x] = true;
	cnt2++;

	for (int i = 0; i < 4; i++) {
		int curY = y + dirY[i];
		int curX = x + dirX[i];

		if (curX < 0 || curY >= n || curY <0 || curY >= n) continue;
		if (isVisited[curY][curX] == false && area[curY][curX] == '1')
			dfs(curY, curX);
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> area[i];
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (isVisited[i][j] == false && area[i][j] == '1') {
				cnt2 = 0;
				dfs(i, j);
				v.push_back(cnt2);
				cnt1++;
			}
		}
	}

	cout << cnt1 << '\n';

	sort(v.begin(), v.end());

	for (int i = 0; i < v.size(); i++) {
		cout << v[i] << '\n';
	}

	return 0;
}