[BOJ/C, C++] 단계별로 풀어보기 - 수학 1

#programming #c #cpp #coding

2026.01.03일자 입니다. 수학 1 풀어보았습니다.
사실 12월 31일에 풀었었는데 입출력부터 풀어보기로 계획이 바뀌어서 전 것들 먼저 올리느라 순서가 밀렸습니다.

2745번 진법 변환

문제 링크
n진수를 10진수로 바꾸는 문제입니다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    string N; int B; cin >> N >> B;
    int res = 0;
    for (int i = 0; i < N.length(); ++i) {
        int temp = N[i];
        res = res * B + (temp <= '9' ? temp - '0' : temp - 'A' + 10);
    }
    cout << res;
}

temp가 '9'보다 작거나 같으면 숫자이므로 '0'만을 차감합니다. 그 이상은 영문자라는 뜻이므로 'A' 차감 이후 10을 더해줍니다.
n진수를 10진수로 변환하려면 각 자릿수에 해당하는 가중치를 곱한 뒤 모두 더하면 됩니다.

res = res * B + (temp <= '9' ? temp - '0' : temp - 'A' + 10);

이것이 변환식이며 호너의 법칙(Horner's rule)이라고 불리는 다항식의 계산량을 줄이는 방법을 사용하였습니다.

11005번 진법 변환 2

문제 링크
10진수를 n진수로 변환하는 문제입니다.

#include <iostream>
#include <string>
using namespace std;
int main() {
    int N, B; cin >> N >> B;
    string res = "";
    while (N) {
        int temp = N % B;
        N /= B;
        res = (char)(temp >= 10 ? temp - 10 + 'A' : temp + '0') + res;
    }
    cout << res;
}

변환 진법으로 나눈 나머지를 역순으로 읽기 위해 + 연산자를 이용하여 결과 문자열 앞에 나머지를 추가하는 방식을 사용했습니다.

2720번 세탁소 사장 동혁

문제 링크
나머지 연산자를 활용하는 기본적인 거스름돈 문제입니다. 해당 문제는 매 선택 현재 상황에서 당장에 최적인 답을 구하는 그리디 알고리즘에 해당합니다. 그리디 알고리즘은 공부할 때 제대로 설명하기로 하고 넘어갑니다.

#include <stdio.h>
int main() {
    int T; scanf("%d", &T);
    for (int i = 0; i < T; ++i) {
        int C; scanf("%d", &C);
        printf("%d ", C / 25); C %= 25;
        printf("%d ", C / 10); C %= 10;
        printf("%d ", C / 5); C %= 5;
        printf("%d\n", C);
    }
}

쉬운 문제여서 c를 이용하여 풀었습니다. 시간 복잡도는 O(1)입니다.

#include <stdio.h>
int main() {
    int T; scanf("%d", &T);
    int coins[] = { 25, 10, 5, 1 };
    while (T--) {
        int C; scanf("%d", &C);
        for (int i = 0; i < 4; ++i) {
            printf("%d ", C / coins[i]);
            C %= coins[i];
        } printf("\n");
    }
}

배열을 이용해 위와 같이 풀 수도 있지만 시간 복잡도는 O(N)입니다.

2903번 중앙 이동 알고리즘

문제 링크
초기는 4개, 1단계 9개, 2단계 25개에서 제곱 규칙을 발견할 수 있고 그 이유는 다음과 같습니다.

각 변의 점의 개수는 모두 동일합니다. 또한 한 변의 점의 개수 만큼 변이 존재한다고 볼 수 있습니다. 따라서 제곱 규칙이 성립합니다.

이제 한 변에 몇 개의 점이 존재하는가에 관한 규칙을 찾아야 합니다.

다음 그림에서 해당 단계의 점의 개수는 전 단계 점의 개수 + 전 단계 - 1 이라는 규칙을 찾을 수 있습니다.

n+1단계는 n단계 두 개를 합쳐 중복된 한 점을 뺀 것이라고 볼 수 있기 때문입니다.

두 가지 규칙을 이용하여 작성한 코드는 다음과 같습니다.

#include <stdio.h>
int main() {
    int N, n = 2; scanf("%d", &N);
    while (N--) n += n - 1;
    printf("%d", n * n);
}

점이 총 두 개인 1단계부터 시작하므로 초기값 n을 2로 설정합니다.

또는 두 번째 규칙을 다음과 같이 해석할 수도 있습니다.

2ⁿ + 1이라는 식을 얻을 수 있는데 이 식을 두 번째 규칙에 적용하면 다음과 같이 코드를 작성할 수 있습니다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int N; cin >> N; int t = pow(2, N) + 1; cout << t * t;
}

제곱을 위해서는 pow 함수를 사용해야 합니다. pow 함수는 double 값을 반환하기 때문에 int 계산을 할 경우 부동소수점 연산으로 오차가 발생할 수 있습니다.

cout << pow(pow(2, N) + 1, 2);

때문에 위의 코드처럼 작성할 경우 오답처리가 됩니다.

2292번 벌집

문제 링크
해당 문제에서 최소 개수의 방이란 해당 방의 단계와 같습니다.

1번 방은 1단계이므로 한 개만 지나면 됩니다. 2번 방부터 7번 방은 2단계이므로 두 개의 방만 지나면 됩니다. 2단계는 1번 방 이후로부터 총 6개로 이루어져 있습니다.
3개의 방을 지나면 되는 3단계 방은 8번 방부터 19번 방, 7번 방 이후로부터 총 12개로 이루어져 있습니다.
따라서 n개의 방을 지나면 되는 n단계는 6*(n-1)개의 방을 가지고 있고 거듭될수록 방의 번호는 6*(n-1)만큼 커집니다.

#include <stdio.h>
int main() {
    int N; scanf("%d", &N);
    int i = 1; N--;
    for (; N > 0; i++) N -= 6 * i;
    printf("%d", i);
}

따라서 어떠한 방에서 1, 6, 12, ..., 6*(n-1)씩 차감하는 방식으로 해당 방의 단계를 구할 수 있습니다.

1193번 분수찾기

문제 링크
벌집 문제와 비슷하다는 느낌을 받은 문제입니다. 분수찾기도 단계를 나누어 규칙을 찾아보았습니다.

1단계는 1/1로 이루어져 있고 2단계는 1/2, 2/1, 3단계는 3/1, 2/2, 1/3으로 이루어져 있습니다.
n단계는 n개의 분수로 이루어져 있으며 단계 내 m번째 분수는 n이 짝수라면 m/n-m+1, 홀수라면 그 역수입니다.

#include <stdio.h>
int main() {
    int X; scanf("%d", &X);
    int i = 1; for (; X > i; i++) X -= i;
    i % 2 == 0 ? printf("%d/%d", X, i - X + 1) : printf("%d/%d", i - X + 1, X);
}

X에서 1, 2, 3, ... 씩 차감하여 몇 단계에 속한 분수인지를 구합니다.
i는 X가 속한 단계, X는 단계 내 몇 번째인지를 나타냅니다.
단계 내 분수의 개수는 해당 단계이므로 X가 i보다 작아지면 X가 i단계에 있다는 뜻이므로 루프를 종료합니다.

2869번 달팽이는 올라가고 싶다

문제 링크
낮에 A미터, 밤에 B미터 하루에 총 A-B미터를 오르고 마지막 날에는 A미터를 오릅니다.

#include <stdio.h>
int main() {
    int A, B, V; scanf("%d %d %d", &A, &B, &V);
    V -= A; A -= B; V% A == 0 ? printf("%d", 1 + V / A) : printf("%d", 2 + V / A);
}