[백준 3678] 카탄의 개척자

[백준 3678] 카탄의 개척자

문제 링크

#include "header.h"
using namespace std;
int c;
int katan[10004];
int frequency[6];
int possible[6] = {1, 1, 1, 1, 1, 1};
void solve() {

    int border = 1;  // 테두리가 몇 겹인지
    int cur = 1;  // 커서
    int inner = 1; //안쪽 타일

    katan[1] = 1;
    frequency[1]++;

    // 해당 인덱스의 인접 행렬 구하기
    for (int i = 2; i <= 10000; i++) {
        for(int p = 1; p<= 5; p++){
            possible[p] = 1;
        }
        //1, 7, 19, 37...는 테두리가 새로 생김
        if(border * 6 + 1 == cur){
            border++;
            cur = 1;
        }
        
        // 마지막 타일
        if(cur == border * 6){
            possible[katan[inner + 1]] = 0;
        }
        
        if(cur % border != 0){ //꼭짓점이 아니라면
            inner++;
            possible[katan[inner]] = 0;
        }

        possible[katan[inner]] = 0;
        possible[katan[i - 1]] = 0;
        cur++;

        // 인접 행렬들을 업데이트 했으니
        // 그 중에서 가장 적게 사용한 것 고르기
        int less = 987654321;
        int lessIdx = 0;

        for (int c = 1; c <= 5; c++) {
            if (possible[c] && less > frequency[c]) {  //가장 적게 쓴 것
                less = frequency[c];
                lessIdx = c;
            }
        }
        katan[i] = lessIdx;
        frequency[lessIdx]++;
    }
}
int main() {
    solve();

    int c;
    cin >> c;
    for (int j = 0; j < c; j++) {
        int num;
        cin >> num;
        cout << katan[num] << endl;
    }

    return 0;
}

• 각 타일마다 인접한 타일들을 찾아 0으로 바꿔준다.
• 새로운 테두리가 생기면 border * 6 + 1 == cur (i = 8, 20, 38… )
  • 2개가 인접한다. i-1, inner
  • 테두리 +1
  • 커서를 1로 초기화
• 테두리의 마지막 타일은 border * 6 == cur (i = 7, 19, 37…)
  • 3개가 인접한다. i-1, inner, inner + 1
• 그 외의 경우에서
  • 꼭지점은 border의 크기만큼 간격을 가지기 때문에 border % cur를 해 주었다.
    1. 꼭지점인 경우
  • 2개 인접한다. i-1, inner
    1. 꼭지점이 아닌 경우
  • 3개 인접한다. i-1, inner + 1, inner
• 인접한 타일들을 제외한 것중, 제일 적게 쓴 것을 구한다.
• 초과 >로 비교하여 만약 같은 숫자가 있을 경우 제일 작은 인덱스를 저장하게 해 주었다.
• 답을 업데이트 후 커서를 +1 하고 반복한다.