문제 1: P1258 소형차 문제 (Car Problem)

문제 설명

두 사람 A와 B가 동시에 출발지에서 목적지까지 최대한 빨리 도착해야 한다. 출발지에는 운전자 외에 한 명만 태울 수 있는 소형차가 한 대 있다. 두 사람의 도보 속도는 동일하며, 차량 속도보다 느리다. 두 사람이 동시에 도착하기 위해 차량을 어떻게 활용해야 하는지 구하시오.

입력 형식

한 줄에 세 개의 실수: 출발지와 목적지 사이의 거리 s, 사람의 도보 속도 a, 차량 속도 b.

출력 형식

두 사람이 동시에 도착하는 데 필요한 최단 시간을 소수점 6자리까지 출력한다.

예제

입력

120 5 25

출력

9.600000

풀이

전체 거리를 s, 차량 속도를 v_car, 사람 속도를 v_walk로 설정한다.

1. 첫 번째 사람(A)이 차량에 탑승하여 t1 시간 동안 이동한 후 하차한다. 이때 A가 이동한 거리는 t1 * v_car, B가 걸어간 거리는 t1 * v_walk이다. 두 사람 사이의 거리는 t1 * (v_car - v_walk)가 된다.
2. 차량이 되돌아가 B를 태우기 위해 이동한다. B와 차량이 만나는 시간 t2는 다음과 같다: t2 = t1 * (v_car - v_walk) / (v_walk + v_car).
3. 이후 t3 시간 동안 차량과 B가 이동하여 A와 동시에 도착한다. A의 총 이동 거리: s = t1 * v_car + (t2 + t3) * v_walk, B의 총 이동 거리: s = t1 * v_walk + (t2 + t3) * v_car.
4. 두 식에서 t1 = t3임을 유도할 수 있다.
5. 이를 통해 t1 = s * (v_walk + v_car) / (v_car^2 + 3 * v_walk * v_car)를 계산한다.
6. 최종 시간 t = 2 * t1 + t2로 구한다.

코드 구현

#define _CRT_SECURE_NO_WARNINGS 
#include <stdio.h>

int main() {
    double dist, speed_walk, speed_car, t1, t2, total_time;
    scanf("%lf %lf %lf", &dist, &speed_walk, &speed_car);

    t1 = (dist * (speed_walk + speed_car)) / (speed_car * speed_car + 3 * speed_walk * speed_car);
    t2 = (t1 * (speed_car - speed_walk)) / (speed_walk + speed_car);
    total_time = 2 * t1 + t2;

    printf("%.6lf", total_time);
    return 0;
}

문제 2: P1125 바보 원숭이 (Dull Monkey)

문제 설명

주어진 단어에서 가장 많이 등장하는 문자의 빈도수(maxn)와 가장 적게 등장하는 문자의 빈도수(minn)의 차이가 소수인 경우, 해당 단어는 "Lucky Word"로 간주된다. 단어는 소문자로만 구성되며 길이는 100 미만이다.

입력 형식

한 줄에 소문자로만 이루어진 단어 하나.

출력 형식

첫 번째 줄: "Lucky Word" 또는 "No Answer".
두 번째 줄: Lucky Word인 경우 maxn - minn 값, 아닌 경우 0.

예제

입력 1

error

출력 1

Lucky Word
2

입력 2

olympic

출력 2

No Answer
0

풀이

strlen 함수로 단어 길이를 구하고, 이중 반복문을 통해 각 문자의 등장 횟수를 계산한다. 배열을 사용하여 최대값과 최소값을 추적한다. 처음에는 최소값을 최대 가능 값(예: 100)으로 초기화한다. 이후 각 문자의 빈도수를 비교하여 최대값과 최소값을 갱신한다. 최종 차이값이 소수인지 판별할 때, 0과 1은 소수가 아님에 주의한다.

코드 구현

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

int main() {
    char word[101];
    scanf("%s", word);
    int len = strlen(word);

    int freq[3] = {0, 0, 100}; // [0]: current count, [1]: max, [2]: min
    for (int i = 0; i < len; i++) {
        int count = 0;
        for (int j = 0; j < len; j++) {
            if (word[i] == word[j]) {
                count++;
            }
        }
        freq[0] = count;
        if (freq[1] < freq[0]) {
            freq[1] = freq[0];
        }
        if (freq[2] > freq[0]) {
            freq[2] = freq[0];
        }
    }

    int diff = freq[1] - freq[2];
    int is_prime = 1; // assume prime

    if (diff < 2) {
        is_prime = 0;
    } else {
        for (int i = 2; i * i <= diff; i++) {
            if (diff % i == 0) {
                is_prime = 0;
                break;
            }
        }
    }

    if (is_prime) {
        printf("Lucky Word\n%d\n", diff);
    } else {
        printf("No Answer\n0\n");
    }

    return 0;
}

문제 3: oibh 본부 구출 (Rescue oibh HQ)

문제 배경

oibh 본부가 갑작스러운 홍수로 침수되었다. 본부 내 일부 중요한 위치에는 벽(*)이 설치되어 있으며, 사방이 벽으로 둘러싸인 영역은 홍수로부터 안전하다. 중요한 영역은 0으로 표시된다.

문제 설명

벽 건설 지도가 주어졌을 때, 홍수로 침수되지 않은 중요 영역(0)의 개수를 구하시오.

입력 형식

첫 줄에 두 양의 정수 x와 y가 주어진다.
다음 x줄에 각각 y개의 문자( * 또는 0)가 주어져 oibh 본부의 지도를 나타낸다.

출력 형식

홍수로 침수되지 않은 0의 개수를 출력한다.

예제

입력

4 5
00000
00*00
0*0*0
00*00

출력

1

풀이

이 문제는 BFS(너비 우선 탐색)를 사용하여 외부에서 접근 가능한 영역을 식별하고, 내부에 고립된 0을 찾는 방식으로 해결한다. 지도를 2차원 배열에 저장하고, 가장자리(테두리)에 있는 0부터 BFS를 시작하여 연결된 모든 0을 방문 처리한다. 이후 방문되지 않은 0의 개수를 세면 홍수로부터 안전한 영역의 수를 얻을 수 있다.

코드 구현 (C)

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

#define MAX 505

char grid[MAX][MAX];
int visited[MAX][MAX];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void bfs(int start_x, int start_y, int rows, int cols) {
    int queue_x[MAX * MAX], queue_y[MAX * MAX];
    int front = 0, rear = 0;

    queue_x[rear] = start_x;
    queue_y[rear] = start_y;
    rear++;
    visited[start_x][start_y] = 1;

    while (front < rear) {
        int cur_x = queue_x[front];
        int cur_y = queue_y[front];
        front++;

        for (int dir = 0; dir < 4; dir++) {
            int nx = cur_x + dx[dir];
            int ny = cur_y + dy[dir];

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && !visited[nx][ny] && grid[nx][ny] == '0') {
                visited[nx][ny] = 1;
                queue_x[rear] = nx;
                queue_y[rear] = ny;
                rear++;
            }
        }
    }
}

int main() {
    int rows, cols;
    scanf("%d %d", &rows, &cols);

    for (int i = 0; i < rows; i++) {
        scanf("%s", grid[i]);
    }

    // 가장자리의 0에서 BFS 시작
    for (int i = 0; i < rows; i++) {
        if (grid[i][0] == '0' && !visited[i][0]) bfs(i, 0, rows, cols);
        if (grid[i][cols-1] == '0' && !visited[i][cols-1]) bfs(i, cols-1, rows, cols);
    }
    for (int j = 0; j < cols; j++) {
        if (grid[0][j] == '0' && !visited[0][j]) bfs(0, j, rows, cols);
        if (grid[rows-1][j] == '0' && !visited[rows-1][j]) bfs(rows-1, j, rows, cols);
    }

    int safe_count = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == '0' && !visited[i][j]) {
                safe_count++;
            }
        }
    }

    printf("%d\n", safe_count);
    return 0;
}