BOJ 12147. Brattleship

🙇‍♀️[Silver III] Brattleship (Small) - 12147

문제 링크

성능 요약

메모리: 2020 KB, 시간: 0 ms

분류

애드 혹, 기하학, 수학

제출 일자

2024년 6월 10일 19:50:21

문제 설명

You're about to play a simplified "battleship" game with your little brother. The board for this game is a rectangular grid with R rows and C columns. At the start of the game, you will close your eyes, and you will keep them closed until the end of the game. Your little brother will take a single rectangular 1 x W ship and place it horizontally somewhere on the board. The ship must always fit entirely on the board, with each cell of the ship occupying exactly one of the grid's cells, and it can never be rotated.

In each turn of the game, you name a cell on the board, and your little brother tells you whether that is a hit (one of the cells occupied by the ship) or a miss. (Your little brother doesn't say which part of the ship was hit -- just that the cell you named has a part of the ship in it.) You have perfect memory, and can keep track of all the information he has given you. Once you have named all of the cells occupied by the ship, the game is over (the ship is sunk), and your score is the number of turns taken. Your goal is to minimize your score.

Although the ship is not supposed to be moved once it is placed, you know that your little brother, who is a brat, plans to cheat by changing the location of the ship whenever he wants, as long as the ship remains horizontal and completely on the board, and the new location is consistent with all the information he has given so far. For example, for a 1x4 board and 1x2 ship, your little brother could initially place the ship such that it overlaps the leftmost two columns. If your first guess was row 1, column 2, he could choose to secretly move the ship to the rightmost two columns, and tell you that (1, 2) was a miss. If your next guess after that was (1, 3), though, then he could not say that was also a miss and move the ship back to its original location, since that would be inconsistent with what he said about (1, 2) earlier.

Not only do you know that your little brother will cheat, he knows that you know. If you both play optimally (you to minimize your score, him to maximize it), what is the lowest score that you can guarantee you will achieve, regardless of what your little brother does?

입력

The first line of the input gives the number of test cases, T. T lines follow, each with three space-separated integers R, C, and W: the number of rows and columns of the board, followed by the width of the ship.

Limits

• 1 ≤ W ≤ C.
• T = 55.
• R = 1.
• 1 ≤ C ≤ 10.

출력

For each test case, output one line containing "Case #x: y", where x is the test case number (starting from 1) and y is the minimum score you can guarantee.

🚀풀이

• 문제 정리
  • 보드는 R x C 크기의 직사각형입니다.
  • 배는 1 x W 크기의 수평 배로 주어집니다.
  • 게임은 여러 라운드로 진행되며, 각 라운드마다 주어진 위치가 배의 일부인지 확인합니다.
  • 배는 절대 회전할 수 없으며, 배치가 동생의 임의적인 위치 변경으로 인해 최적의 경우로 옮겨질 수 있습니다.
  • 목표는 최소한의 라운드 수로 배의 위치를 정확히 찾는 것입니다.
• 해결 전략
  • 기본 개념: R행 C열의 보드에서, 배의 길이 W가 주어질 때 최악의 경우를 고려하여 최소 추측 횟수를 계산합니다.
• 최적의 전략:
  • 각 행을 독립적으로 생각하여 각 행마다 최소한의 시도로 배를 찾습니다.
  • 각 행에서의 최소 시도 횟수는 C // W입니다. 이 값은 각 행에서 W 길이의 배를 찾기 위해 필요한 최소한의 시도입니다.
  • 배가 포함된 마지막 위치를 찾기 위해 추가적인 W-1 시도가 필요합니다.
  • 여러 행을 고려하여 최종 점수를 계산합니다.

설명

1. 기본 시도 횟수: 각 행에서 C / W만큼의 시도 횟수가 필요합니다. 이는 각 행에서 배의 위치를 찾기 위해 필요한 최소 시도 횟수입니다.
2. 추가 시도 횟수: 배의 정확한 위치를 찾기 위해 마지막으로 W - 1번의 추가 시도가 필요합니다.
3. 최종 시도 횟수: 모든 행에 대해 기본 시도 횟수를 계산한 후, 추가 시도 횟수를 더하여 최종 시도 횟수를 계산합니다.
4. 추가 점검: C % W != 0일 경우 한 번 더 시도해야 합니다.

void solve()
{
    int T;
    cin >> T;

    for (int t = 1; t <= T; ++t) 
    {
        int R, C, W;
        cin >> R >> C >> W;

        // 각 행마다 W 길이의 배를 찾기 위해 필요한 최소 시도 횟수
        int moves_per_row = C / W;

        // 마지막 부분에서 배의 위치를 정확히 찾기 위해 W-1번의 추가 시도가 필요
        int additional_moves = W - 1;

        // 모든 행에서 기본적인 시도 횟수를 계산
        int total_moves = moves_per_row * R + additional_moves;

        // 배가 정확히 C와 일치하지 않을 경우를 위해 추가 점검
        if (C % W != 0) 
        {
            total_moves += 1;
        }

        cout << "Case #" << t << ": " << total_moves << '\n';
    }
}

🚀코드

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <math.h>
#include <climits>

using namespace std;

void solve()
{
    int T;
    cin >> T;

    for (int t = 1; t <= T; ++t) 
    {
        int R, C, W;
        cin >> R >> C >> W;

        // 각 행마다 W 길이의 배를 찾기 위해 필요한 최소 시도 횟수
        int moves_per_row = C / W;

        // 마지막 부분에서 배의 위치를 정확히 찾기 위해 W-1번의 추가 시도가 필요
        int additional_moves = W - 1;

        // 모든 행에서 기본적인 시도 횟수를 계산
        int total_moves = moves_per_row * R + additional_moves;

        // 배가 정확히 C와 일치하지 않을 경우를 위해 추가 점검
        if (C % W != 0) 
        {
            total_moves += 1;
        }

        cout << "Case #" << t << ": " << total_moves << '\n';
    }
}

int main()
{
	FILE* stream;
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	freopen_s(&stream, "input.txt", "rt", stdin);

	solve();

	return 0;
}