<aside> 1️⃣

1740번 거듭제곱

3의 거듭제곱의 합으로 표현되는 N번째로 작은 수 구하기

</aside>

#include <stdio.h>

//3진수로 해석해 풀기
int main() {
    long long N;
    scanf("%lld", &N);

    long long result = 0;
    long long power = 1; //3^0

    while (N > 0) {
        if (N & 1) { //이진수에서 1인 자리 → 3의 거듭제곱 더하기
            result += power;
        }
        power *= 3; //다음 3의 제곱
        N >>= 1; //이진수 다음 자리로
    }

    printf("%lld\\n", result);
    return 0;
}

<aside> 2️⃣

1966번 프린터 큐

프린터 출력 규칙

• 기본적으로 맨 앞 문서 출력
• 맨 앞보다 높은 중요도를 가진 문서가 하나라도 있는 경우 맨 앞 문서를 뒤로 보냄

M번째 문서가 몇 번째로 인쇄되는지 구하기

</aside>

• 오답 코드 - 시간초과

#include <stdio.h>

typedef struct {
    int priority;
    int index;
} Document;

int main() {
    int T;
    if (scanf("%d", &T) != 1) return 0;

    while (T--) {
        int N, M;
        scanf("%d %d", &N, &M);

        const int CAP = 1000;
        Document queue[CAP];
        int priorityCount[10] = {0}; //중요도 세기

        for (int i = 0; i < N; i++) {
            int p;
            scanf("%d", &p);
            queue[i].priority = p;
            queue[i].index = i;
            priorityCount[p]++;
        }

        int front = 0; //읽을 위치
        int back = N; //다음에 쓸 위치
        int printed = 0;

        while (1) {
            Document current = queue[front % CAP];
            front++;

            //현재보다 높은 중요도가 있는지 확인
            int hasHigher = 0;
            for (int p = current.priority + 1; p <= 9; p++) {
                if (priorityCount[p] > 0) {
                    hasHigher = 1;
                    break;
                }
            }

            if (hasHigher) {
                //뒤로 보내기
                queue[back % CAP] = current;
                back++;
            } else {
                //인쇄
                printed++;
                priorityCount[current.priority]--;

                if (current.index == M) {
                    printf("%d\\n", printed);
                    break;
                }
            }
        }
    }
    return 0;
}