[C언어 백준 풀이][Bronze] 4153번 : 직각삼각형 / 10250번 : ACM 호텔 / 2798번 : 블랙잭 / 11050번 : 이항 계수 1

지난 번의 프로그래밍 문제 사이트 백준 Online Judge의 Solved.ac CLASS 1 에센셜 문제들에 이어 CLASS 2 문제들도 해결해보도록 하겠습니다.

단순히 쉬운 문제들로 문제 수를 채우기보다는 에센셜 문제들을 우선적으로 해결해보도록 하겠습니다.

 

이번 포스트에서 풀어볼 문제들은 그 중에서도 쉬운 편인 Bronze에 해당하는 위의 4문제입니다.

각 문제의 이름은 4153번 직각삼각형, 10250번 ACM 호텔, 2798번 블랙잭, 11050번 이항 계수 1입니다.

 

 

4153번 : 직각삼각형

 

여러 개의 테스트케이스에 대해 각 입력으로 세 변의 길이가 주어질 때, 이 세 변으로 이루어진 삼각형이 직각삼각형인지를 검사하는 문제입니다.

테스트케이스의 종료는 0 0 0의 입력으로 수행되기 때문에 무한 루프를 구현하여야 합니다.

 

#include<stdio.h>

void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main() {
    int a, b, c;
    while(1) {
        scanf("%d %d %d", &a, &b, &c);
        if(!a && !b && !c) return 0;
        if(b > c) swap(&b, &c);
        if(a > b) swap(&a, &b);
        if(b > c) swap(&b, &c);
        if(a*a + b*b == c*c) printf("right\n");
        else printf("wrong\n");
    }
}

 

먼저 이 문제를 해결하기 위해서는 피타고라스 정리를 사용하기 위해 세 수를 크기순으로 정렬해주어야 합니다.

저의 경우에는 오름차순으로 정렬하였습니다. (a <= b <= c)

일반적인 정렬은 정렬 알고리즘대로 구현해야 하지만 수가 3개이기 때문에 swap 함수를 활용하고 3번의 조건부 swap으로 정렬을 했습니다.

사실 이 부분은 삼항연산자를 여러 번 사용해도 됩니다.

그리고 나서 피타고라스 정리를 사용해서 직각삼각형에 해당하는지 검사하였습니다.

이 부분에서 주의할 점은 math.h의 sqrt 함수를 사용하면 오차가 발생할 수 있기 때문에 반드시 양변의 제곱으로 비교해주어야 합니다.

 

 

10250번 : ACM 호텔

 

위의 설명대로 빈 호텔이 있을 때 빠른 호수 순으로, 동일 호수일 때는 낮은 층수 순으로 방을 배정한다고 할 때 N번째 손님이 배정받을 방의 호수를 출력하는 문제입니다.

우선 순위를 이용하여 규칙성을 찾고 식을 작성해야 합니다.

 

#include<stdio.h>

int main() {
    int T, H, W, N, room;
    scanf("%d", &T);
    for(int i=0; i<T; i++) {
        scanf("%d %d %d", &H, &W, &N);
        if(N%H) room = (N%H)*100 + N/H + 1;
        else room = H*100 + N/H;
        printf("%d\n", room);
    }
}

 

방의 배정은 호수가 빠른 것이 우선으로 일어나고 호텔 정원수를 초과하는 N의 입력은 일어나지 않기 때문에 호텔의 층수만 고려해주면 됩니다.

두어줄만 배정을 직접 해보면 배정되는 층수는 N을 H으로 나눈 나머지와 연관이 있고, 배정되는 호수는 N을 H으로 나눈 몫과 연관이 있음을 알 수 있습니다.

나머지는 %과 / 연산으로 표현이 가능하지만 예외는 N이 H으로 나누어떨어지는 경우입니다.

0층이나 0호실을 배정할 수는 없기 때문에 N이 H로 나누어떨어지는 경우 H층을 배정해주면 됩니다.

그 외에는 고려해야 할 예외 사항이 없으므로 하나의 조건문으로 쉽게 해결이 됩니다.

 

 

2798번 : 블랙잭

 

입력받은 N개의 카드 중에서 3장을 골라 M을 넘지 않는 M에 가장 가까운 합을 출력하는 문제입니다.

N이 최대 100이기 때문에 시간 제한은 신경쓰지 않아도 되지만 구조 자체는 어느 정도 일반화시켜서 코드를 작성해야 합니다.

카드 최대치 100장이 모두 최댓값인 10만으로 주어져도 모든 합이 1천만을 넘어가지 않기 때문에 자료형의 범위를 고려하지는 않아도 됩니다.

 

#include<stdio.h>

int main() {
    int N, M, card[105], max = 0;
    scanf("%d %d", &N, &M);
    for(int i=0; i<N; i++) scanf("%d", &card[i]);
    for(int i=0; i<N; i++)
        for(int j=i+1; j<N; j++)
            for(int k=j+1; k<N; k++)
                if(card[i]+card[j]+card[k] > max && card[i]+card[j]+card[k] <= M) max = card[i]+card[j]+card[k];
    printf("%d", max);
}

 

카드가 100장이므로 i, j, k에 대한 루프를 구성하여 3중 반복문으로 모든 경우의 수를 탐색하는 것이 가장 쉽습니다.

변수나 괄호의 생략을 위해 굳이 sum 변수를 사용하지 않고 바로 합해서 비교 및 변수 갱신을 수행하도록 작성하였습니다.

i가 0~N-1까지 탐색을 한다면 그 안쪽 루프의 j는 i+1~N-1까지 탐색을 해주고 그 안쪽 루프의 k는 j+1~N-1까지 탐색을 해야 중복되는 카드 없이 세 장이 모두 다른 카드를 선택할 수 있습니다.

 

 

11050번 : 이항 계수 1

 

입력받은 N과 K에 대해 nCk를 계산하여 출력하는 문제입니다. (이항계수와 같은 의미)

nCk 연산은 (N*(N-1)* ... *(N-k+1))/k!이므로 이 식 그대로 코드로 구현하면 됩니다.

N이 10 이하이기 떄문에 10!을 계산하더라도 정수 범위를 벗어나지 않으므로 구현에 있어서 다른 전략을 사용해야 한다던가 식을 더욱 단순화 시킬 필요는 없습니다.

 

#include<stdio.h>

int main() {
    int N, K, ans = 1;
    scanf("%d %d", &N, &K);
    for(int i=N; i>N-K; i--) ans *= i;
    for(int i=K; i>=1; i--) ans /= i;
    printf("%d", ans);
}

 

for문을 이용하면 변수 범위의 조작이 쉽기 때문에 for문을 2번 사용하여 구현하였습니다.

ans = 1로 초기값을 설정해야 바로 for문에서 곱셈 연산을 사용할 수 있습니다.