BOJ 16722

25 Feb 2020 • ProblemSolving

결! 합!

문제출처

문제 해석

  • 도형의 모양, 색, 배경색 세가지 속성이 각각 다르게 조합된 27장의 그림 중 아홉장의 그림들로 결합게임을 해서 최종적으로 얻는 점수를 맞추는 문제입니다.
  • 해당 게임에는 결,합 명령어가 있습니다.
  • ‘합’이란 그림의 세가지 속성이 모두 같거나 모두 다른 세장의 그림 조합입니다.
  • '’합’외치기 : 명령어 H와 서로다른 세장의 번호가 주어졌을 때, 해당 세장이 합을 이루면서 이전에 외친적이 없는 그림조합이면 +1점, 아니면 -1점을 획득합니다.
  • ‘결’외치기 : 아홉장의 그림으로 조합가능한 ‘합’들 중 외치지 않은 합이 더이상 없고 결을 통해 점수를 얻은적이 없다면 +3점, 아니면 -1점을 획득합니다.

설계(10)

  • 단순 시뮬레이션 문제입니다.
  • 주어진 9장의 그림을 조합하여 합을 만들 수 있는 세 그림 번호(번호는 오름차순이어야 합니다)조합을 3차원 배열에 체크합니다. 동시에 가능한 조합 수를 카운트합니다.
  • H가 주어졌을 때, 3개의 번호를 오름차순으로 정렬한 후, visited체크가 안되어있고 hap이 true이면 체크하도록 합니다. 이와 동시에 가능한 조합수를 한개씩 빼줍니다.
  • G가 주어졌을 때, 이전에 결을 통해 점수를 얻었는지의 여부를 알기 위해 is_finished bool형 변수를 이용하였고, 해당 변수가 false이고 합이 가능한 조합수가 0이면 +3을 하도록 하였습니다.

구현(20)

코드
#include <iostream>
#include <vector>
#include <algorithm>
#define MAXN 9
using namespace std;

char map[3][3][10] = { {"CIRCLE","SQUARE","TRIANGLE"},
{"RED","YELLOW","BLUE"},
{"BLACK","GRAY","WHITE"} };
int arr[MAXN][3];
bool hap[MAXN][MAXN][MAXN];
bool visited[MAXN][MAXN][MAXN];
bool check_hap(int arr1[] , int arr2[], int arr3[]){
    int cnt = 0;
    for (int i = 0; i < 3; i++){
        if (arr1[i] == arr2[i] && arr2[i] == arr3[i]) cnt++;
        else if (arr1[i]!= arr2[i] && arr2[i]!=arr3[i] && arr1[i] != arr3[i]) cnt++;
    }
    return (cnt==3);
}
bool is_finished;
int hap_cnt;
int N;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    for (int i = 0 ;i < MAXN; i++){
        for (int j =0 ;j < 3; j++){
            string s;
            cin >> s;
            for (int k = 0; k < 3; k++){
                if (s == map[j][k]){
                    arr[i][j] = k;
                    break;
                }
            }
        }
    }
    for (int i= 0 ; i < MAXN; i++){
        for (int j = i+1; j < MAXN; j++){
            for (int k = j+1; k<MAXN; k++){
                if (check_hap(arr[i],arr[j],arr[k])){
                    hap[i][j][k] = true;
                    hap_cnt++;
                }
            }
        }
    }
    cin >> N;
    int ans = 0 ;
    for (int i = 0 ; i < N;i++){
        char tmp;
        cin >> tmp;
        if (tmp == 'H'){
            int order[3]={0,};
            cin >> order[0] >> order[1] >> order[2];
            order[0]--;
            order[1]--;
            order[2]--;
            sort(order,order+3);
            if (!visited[order[0]][order[1]][order[2]] && hap[order[0]][order[1]][order[2]]){
                visited[order[0]][order[1]][order[2]] = true;
                hap_cnt--;
                ans++;
            }
            else{
                ans--;
            }
        }
        else{
            if (!is_finished && hap_cnt==0) {
                is_finished = true;
                ans+=3;
            }
            else ans--;
        }
    }
    cout << ans <<"\n";
    return 0;
}
디버깅
제출결과
  • 0ms

마무리

  • 단순 시뮬레이션 문제였습니다. 가능한 조합수가 적어 완전탐색을 이용하면 되었고, 하라는데로만 하면 되는 문제였습니다.
 BOJ

Related Posts