TIL 코딩공장

백준 C언어 공부 2024.11.25
10250번 ACM 호텔

1. 문제
ACM 호텔 매니저 지우는 손님이 도착하는 대로 빈 방을 배정하고 있다. 
고객 설문조사에 따르면 손님들은 호텔 정문으로부터 걸어서 가장 짧은 거리에 있는 방을 선호한다고 한다. 
여러분은 지우를 도와 줄 프로그램을 작성하고자 한다. 
즉 설문조사 결과 대로 호텔 정문으로부터 걷는 거리가 가장 짧도록 방을 배정하는 프로그램을 작성하고자 한다.

문제를 단순화하기 위해서 호텔은 직사각형 모양이라고 가정하자. 
각 층에 W 개의 방이 있는 H 층 건물이라고 가정하자 (1 ≤ H, W ≤ 99). 
그리고 엘리베이터는 가장 왼쪽에 있다고 가정하자(그림 1 참고). 
이런 형태의 호텔을 H × W 형태 호텔이라고 부른다. 
호텔 정문은 일층 엘리베이터 바로 앞에 있는데, 정문에서 엘리베이터까지의 거리는 무시한다. 
또 모든 인접한 두 방 사이의 거리는 같은 거리(거리 1)라고 가정하고 호텔의 정면 쪽에만 방이 있다고 가정한다.

그림 1. H = 6 이고 W = 12 인 H × W 호텔을 간략하게 나타낸 그림

방 번호는 YXX 나 YYXX 형태인데 여기서 Y 나 YY 는 층 수를 나타내고 XX 는 엘리베이터에서부터 세었을 때의 번호를 나타낸다. 
즉, 그림 1 에서 빗금으로 표시한 방은 305 호가 된다.

손님은 엘리베이터를 타고 이동하는 거리는 신경 쓰지 않는다. 
다만 걷는 거리가 같을 때에는 아래층의 방을 더 선호한다. 
예를 들면 102 호 방보다는 301 호 방을 더 선호하는데, 102 호는 거리 2 만큼 걸어야 하지만 301 호는 거리 1 만큼만 걸으면 되기 때문이다. 
같은 이유로 102 호보다 2101 호를 더 선호한다.

여러분이 작성할 프로그램은 초기에 모든 방이 비어있다고 가정하에 이 정책에 따라 N 번째로 도착한 손님에게 배정될 방 번호를 계산하는 프로그램이다. 
첫 번째 손님은 101 호, 두 번째 손님은 201 호 등과 같이 배정한다. 
그림 1 의 경우를 예로 들면, H = 6이므로 10 번째 손님은 402 호에 배정해야 한다.

2. 입력
프로그램은 표준 입력에서 입력 데이터를 받는다. 
프로그램의 입력은 T 개의 테스트 데이터로 이루어져 있는데 T 는 입력의 맨 첫 줄에 주어진다. 
각 테스트 데이터는 한 행으로서 H, W, N, 세 정수를 포함하고 있으며 각각 호텔의 층 수, 각 층의 방 수, 몇 번째 손님인지를 나타낸다(1 ≤ H, W ≤ 99, 1 ≤ N ≤ H × W). 

3. 출력
프로그램은 표준 출력에 출력한다. 
각 테스트 데이터마다 정확히 한 행을 출력하는데, 
내용은 N 번째 손님에게 배정되어야 하는 방 번호를 출력한다.

>>>코드

#include<stdio.h>

int main(void){
    int t;
    scanf("%d", &t);
    
    for (int i = 0; i<t; i++){
        int h, w, n;
        scanf("%d %d %d", &h, &w, &n);
        int room_num;
        if (n%h == 0) room_num = h*100 + n/h;
        else room_num = n%h*100 + n/h+1;
        printf("%d\n", room_num);
    }
    
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/10250

백준 C언어 공부 2024.11.24
1018번 체스판 다시 칠하기

1. 문제
지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다.
어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 
지민이는 이 보드를 잘라서 8×8 크기의 체스판으로 만들려고 한다.

체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 
구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 
변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 
따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 
하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다.

보드가 체스판처럼 칠해져 있다는 보장이 없어서, 
지민이는 8×8 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 
당연히 8*8 크기는 아무데서나 골라도 된다. 
지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 N과 M이 주어진다. 
N과 M은 8보다 크거나 같고, 50보다 작거나 같은 자연수이다. 
둘째 줄부터 N개의 줄에는 보드의 각 행의 상태가 주어진다. 
B는 검은색이며, W는 흰색이다.

3. 출력
첫째 줄에 지민이가 다시 칠해야 하는 정사각형 개수의 최솟값을 출력한다.

>>>코드

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(void){
    int n, m;
    scanf("%d %d", &n, &m);
    
    char **chess = (char **)malloc(n * sizeof(char *));
    for (int i = 0; i<n; i++){
        chess[i] = (char *)malloc(m+1);
        scanf("%s", chess[i]);
    }
    
    int cnt = 0, min = 64;
    for (int i = 0; i<n-7; i++){
        for (int j = 0; j<m-7; j++){
            cnt = 0;
            if (chess[i][j] == 'B'){
                for (int k = 0; k<8; k++){
                    for (int l = 0; l<8; l++){
                        if (chess[i+k][j+l] == 'W' && (k+l)%2 == 0) cnt++;
                        else if (chess[i+k][j+l] == 'B' && (k+l)%2 == 1) cnt++;
                     }
                }
            }
            else{
                for (int k = 0; k<8; k++){
                    for (int l = 0; l<8; l++){
                        if (chess[i+k][j+l] == 'B' && (k+l)%2 == 0) cnt++;
                        else if (chess[i+k][j+l] == 'W' && (k+l)%2 == 1) cnt++;
                     }
                }
            }
            if (cnt > 32) cnt = 64-cnt;
            if (cnt < min) min = cnt;
        }
    }
    
    printf("%d", min);
    
    for (int i = 0; i<n; i++){
        free(chess[i]);
    }
    
    free(chess);
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/1018

백준 C언어 공부 2024.11.23
1966번 프린터 큐

1. 문제
여러분도 알다시피 여러분의 프린터 기기는 여러분이 인쇄하고자 하는 문서를 
인쇄 명령을 받은 ‘순서대로’, 즉 먼저 요청된 것을 먼저 인쇄한다. 
여러 개의 문서가 쌓인다면 Queue 자료구조에 쌓여서 FIFO - First In First Out - 에 따라 인쇄가 되게 된다. 
하지만 상근이는 새로운 프린터기 내부 소프트웨어를 개발하였는데, 
이 프린터기는 다음과 같은 조건에 따라 인쇄를 하게 된다.

1) 현재 Queue의 가장 앞에 있는 문서의 ‘중요도’를 확인한다.
2) 나머지 문서들 중 현재 문서보다 중요도가 높은 문서가 하나라도 있다면, 
이 문서를 인쇄하지 않고 Queue의 가장 뒤에 재배치 한다. 그렇지 않다면 바로 인쇄를 한다.

예를 들어 Queue에 4개의 문서(A B C D)가 있고, 중요도가 2 1 4 3 라면 
C를 인쇄하고, 다음으로 D를 인쇄하고 A, B를 인쇄하게 된다.

여러분이 할 일은, 현재 Queue에 있는 문서의 수와 중요도가 주어졌을 때, 
어떤 한 문서가 몇 번째로 인쇄되는지 알아내는 것이다. 
예를 들어 위의 예에서 C문서는 1번째로, A문서는 3번째로 인쇄되게 된다.

2. 입력
첫 줄에 테스트케이스의 수가 주어진다. 각 테스트케이스는 두 줄로 이루어져 있다.

테스트케이스의 첫 번째 줄에는 문서의 개수 N(1 ≤ N ≤ 100)과, 
몇 번째로 인쇄되었는지 궁금한 문서가 현재 Queue에서 몇 번째에 놓여 있는지를 나타내는 정수 M(0 ≤ M < N)이 주어진다. 
이때 맨 왼쪽은 0번째라고 하자. 
두 번째 줄에는 N개 문서의 중요도가 차례대로 주어진다. 
중요도는 1 이상 9 이하의 정수이고, 중요도가 같은 문서가 여러 개 있을 수도 있다.

3. 출력
각 테스트 케이스에 대해 문서가 몇 번째로 인쇄되는지 출력한다.

>>>코드

#include<stdio.h>

int main(void){
    int t;
    scanf("%d", &t);
    
    while (t--){
        int n, m;
        scanf("%d %d", &n, &m);
        
        int printer[100] = {0}, priority[10] = {0};
        for (int i = 0; i<n; i++){
            scanf("%d", &printer[i]);
            priority[printer[i]]++; 
        }
        int odr = 0, prior = 9;
        while (priority[prior] == 0 && prior > 0) prior--;
        
        while (prior){
            for (int i = 0; i<n; i++){
                if (printer[i] == prior){
                    priority[prior]--;
                    odr++;
                    if (i == m){
                        printf("%d\n", odr);
                        goto next_case;
                    }
                }
                while (priority[prior] == 0 && prior > 0) prior--;
            }
        }
    next_case:;
    }
    
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/1966

백준 C언어 공부 2024.11.22
2231번 분해합

1. 문제
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 
어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 
예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 
따라서 245는 256의 생성자가 된다. 
물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 
반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

2. 입력
첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

3. 출력
첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

>>>코드

#include<stdio.h>

int main(){
    int n;
    scanf("%d", &n);
    
    int num = 1;
    while (num <= n){
        int result = num;
        int m = num;
        while (m>0){
            result += m%10;
            m /= 10;
        }
        if (result == n) break;
        num++;
    }
    if (num < n) printf("%d", num);
    else printf("0");
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/2231

백준 C언어 공부 2024.11.21
2920번 음계

1. 문제
다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 
이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. 
c는 1로, d는 2로, ..., C를 8로 바꾼다.

1부터 8까지 차례대로 연주한다면 ascending, 
8부터 1까지 차례대로 연주한다면 descending, 
둘 다 아니라면 mixed 이다.

연주한 순서가 주어졌을 때, 
이것이 ascending인지, descending인지, 아니면 mixed인지 판별하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 8개 숫자가 주어진다. 
이 숫자는 문제 설명에서 설명한 음이며, 1부터 8까지 숫자가 한 번씩 등장한다.

3. 출력
첫째 줄에 ascending, descending, mixed 중 하나를 출력한다.

>>>코드

#include<stdio.h>

int main(){
    int n[8];
    
    for (int i = 0; i<8; i++){
        scanf("%d", &n[i]);
    }
    
    int flag_a = 1;
    int flag_d = 1;

    // 배열 검사
    for (int i = 0; i < 8; i++) {
        if (n[i] != i + 1) {
            flag_a = 0;
        }
        if (n[i] != 8 - i) {
            flag_d = 0;
        }
    }

    if (flag_a) {
        printf("ascending");
    } 
    else if (flag_d) {
        printf("descending");
    } 
    else {
        printf("mixed");
    }

    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/2920

백준 C언어 공부 2024.11.20
2577번 숫자의 개수

1. 문제
세 개의 자연수 A, B, C가 주어질 때 A × B × C를 계산한 결과에 
0부터 9까지 각각의 숫자가 몇 번씩 쓰였는지를 구하는 프로그램을 작성하시오.

예를 들어 
A = 150, B = 266, C = 427 이라면 
A × B × C = 150 × 266 × 427 = 17037300 이 되고, 
계산한 결과 17037300 에는 0이 3번, 1이 1번, 3이 2번, 7이 2번 쓰였다.

2. 입력
첫째 줄에 A, 둘째 줄에 B, 셋째 줄에 C가 주어진다. 
A, B, C는 모두 100보다 크거나 같고, 1,000보다 작은 자연수이다.

3. 출력
첫째 줄에는 A × B × C의 결과에 0 이 몇 번 쓰였는지 출력한다. 
마찬가지로 둘째 줄부터 열 번째 줄까지 A × B × C의 결과에 
1부터 9까지의 숫자가 각각 몇 번 쓰였는지 차례로 한 줄에 하나씩 출력한다.

>>>코드

#include<stdio.h>

int main(){
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result = a*b*c;
    int cnt[10] = {0};
    while (result > 0){
        cnt[result%10]++;
        result /= 10;
    }
    
    for (int i = 0; i<10; i++){
        printf("%d\n", cnt[i]);
    }
    
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/2577

백준 C언어 공부 2024.11.19
8958번 OX퀴즈

1. 문제
"OOXXOXXOOO"와 같은 OX퀴즈의 결과가 있다. 
O는 문제를 맞은 것이고, X는 문제를 틀린 것이다. 
문제를 맞은 경우 그 문제의 점수는 그 문제까지 연속된 O의 개수가 된다. 
예를 들어, 10번 문제의 점수는 3이 된다.

"OOXXOXXOOO"의 점수는 1+2+0+0+1+0+0+1+2+3 = 10점이다.

OX퀴즈의 결과가 주어졌을 때, 점수를 구하는 프로그램을 작성하시오.

2. 입력
첫째 줄에 테스트 케이스의 개수가 주어진다. 
각 테스트 케이스는 한 줄로 이루어져 있고, 길이가 0보다 크고 80보다 작은 문자열이 주어진다. 
문자열은 O와 X만으로 이루어져 있다.

3. 출력
각 테스트 케이스마다 점수를 출력한다.

>>>코드

#include<stdio.h>
#include<string.h>

int main(){
    int n;
    scanf("%d", &n);
    
    char ox[81];
    for (int i = 0; i<n; i++){
        scanf("%s", ox);
        
        char *p;
        int length = strlen(ox), score = 1, final_score = 0;
        for (p = ox; p<ox+length; p++){
            if (*p == 'O'){
                final_score += score;
                score++;
            }
            else{
                score = 1;
            }
        }
        
        printf("%d\n", final_score);
    }
    
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/8958

백준 C언어 공부 2024.11.18
31403번 A+B-C

1. 문제
JavaScript에서 +, -은 수에 대해서는 일반적인 의미의 덧셈 뺄셈의 의미를 가지고 있습니다. 
하지만 문자열에 대해서 +는 두 문자열을 이어붙이라는 의미이고, 
-는 양쪽 문자열을 수로 해석한 이후에 빼라는 의미입니다.

 A, B, C를 각각 수와 문자열로 생각했을 때 A+B-C를 출력하세요.

2. 입력
첫 줄에는 정수 A가 주어집니다. 
(1 <= A <= 1,000) 

둘째 줄에는 정수 B가 주어집니다. 
(1 <= B <= 1,000) 

셋째 줄에는 정수 C가 주어집니다. 
(1 <= C <= 1,000) 

주어지는 모든 수는 0으로 시작하지 않는 양의 정수입니다.

3. 출력
첫 줄에는 A, B, C를 수로 생각했을 때, A+B-C를 출력하세요.
둘째 줄에는 A, B, C를 문자열로 생각했을 때, A+B-C를 출력하세요.

>>>코드1. atoi 함수와 strcat 함수 사용

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
    char a[5], b[5], c[5];
    scanf("%s", a);
    scanf("%s", b);
    scanf("%s", c);
    
    int result1 = atoi(a) + atoi(b) - atoi(c);
    char strcal[9] = "\0";
    strcpy(strcal, a);
    strcat(strcal, b);
    int result2 = atoi(strcal) - atoi(c);
    
    printf("%d\n", result1);
    printf("%d\n", result2);
    
    return 0;
}

>>코드2. b의 자릿수를 계산하여 문자열 계산 수행하기

#include<stdio.h>

int main(){
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result1 = a + b - c;
    
    int ten = 10, i;
    for (int i = 0; i<4; i++){
        if (b < ten) break;
        ten *= 10;
    }
    int result2 = a * ten + b - c;
    
    printf("%d\n", result1);
    printf("%d\n", result2);
    
    return 0;
}

4. 문제링크
https://www.acmicpc.net/problem/31403