BOJ 20057. 마법사 상어와 토네이도

24-03-18

🙇‍♀️[Gold III] 마법사 상어와 토네이도 - 20057

문제 링크

성능 요약

메모리: 3084 KB, 시간: 28 ms

분류

구현, 시뮬레이션

제출 일자

2024년 3월 18일 16:30:24

문제 설명

마법사 상어가 토네이도를 배웠고, 오늘은 토네이도를 크기가 N×N인 격자로 나누어진 모래밭에서 연습하려고 한다. 위치 (r, c)는 격자의 r행 c열을 의미하고, A[r][c]는 (r, c)에 있는 모래의 양을 의미한다.

토네이도를 시전하면 격자의 가운데 칸부터 토네이도의 이동이 시작된다. 토네이도는 한 번에 한 칸 이동한다. 다음은 N = 7인 경우 토네이도의 이동이다.

토네이도가 한 칸 이동할 때마다 모래는 다음과 같이 일정한 비율로 흩날리게 된다.

토네이도가 x에서 y로 이동하면, y의 모든 모래가 비율과 α가 적혀있는 칸으로 이동한다. 비율이 적혀있는 칸으로 이동하는 모래의 양은 y에 있는 모래의 해당 비율만큼이고, 계산에서 소수점 아래는 버린다. α로 이동하는 모래의 양은 비율이 적혀있는 칸으로 이동하지 않은 남은 모래의 양과 같다. 모래가 이미 있는 칸으로 모래가 이동하면, 모래의 양은 더해진다. 위의 그림은 토네이도가 왼쪽으로 이동할 때이고, 다른 방향으로 이동하는 경우는 위의 그림을 해당 방향으로 회전하면 된다.

토네이도는 (1, 1)까지 이동한 뒤 소멸한다. 모래가 격자의 밖으로 이동할 수도 있다. 토네이도가 소멸되었을 때, 격자의 밖으로 나간 모래의 양을 구해보자.

입력

첫째 줄에 격자의 크기 N이 주어진다. 둘째 줄부터 N개의 줄에는 격자의 각 칸에 있는 모래가 주어진다. r번째 줄에서 c번째 주어지는 정수는 A[r][c] 이다.

출력

격자의 밖으로 나간 모래의 양을 출력한다.

🚀풀이

토네이도 방향으로 이동을 구현하는 방법을 알아야한다.

토네이도 방향으로 이동하려면 방향이 두번 바뀔 때 마다 이동하는 칸수가 하나 증가하는 규칙을 알아야한다.

문제의 예시를 그래도 사용하면 왼쪽으로 한 칸, 아래로 한 칸 이동하면 오른쪽으로 두 칸, 위로 두 칸 이동한다.
그 뒤엔 다시 왼쪽으로 세 칸, 아래로 세 칸 이동한다.

이러한 규칙을 바탕으로 토네이도 움직임 로직을 구현하고 해당 위치에서 방향값을 바탕으로 좌표 계산을 통해 값을 구해주면 된다.

나의 경우에는 한번 움직일 때 마다 하나하나 좌표를 계산해서 보드안을 채워줬다.

🚀코드

#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>

using namespace std;

int n;
int dy[] = { 0, 1, 0, -1 };
int dx[] = { -1, 0, 1, 0 };
vector<vector<int>> board;

void move()
{
	pair<int, int> pos = { n / 2 + 1, n / 2 + 1};

	int idx = 1, dir = 0;
	int total = 0, ten = 0, seven = 0, five = 0, two = 0, one = 0, alpa = 0, ny = 0, nx = 0;
	while (true)
	{
		if (pos.first == 1 && pos.second == 1)
			break;

		for (int i = 0; i < idx; ++i)
		{
			if (pos.first == 1 && pos.second == 1)
				break;

			int nextY = pos.first + dy[dir];
			pos.first = nextY;
			int nextX = pos.second + dx[dir];
			pos.second = nextX;

			// 모래 분배하기
			total = board[pos.first][pos.second];
			ten = total * 10 / 100;
			seven = total * 7 / 100;
			five = total * 5 / 100;
			two = total * 2 / 100;
			one = total * 1 / 100;
			alpa = total - (2 * ten + 2 * seven + 1 * five + 2 * two + 2 * one);
			board[pos.first][pos.second] = 0;

			// 알파 더해주기
			ny = pos.first + dy[dir];
			nx = pos.second + dx[dir];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += alpa;
			}

			// 10퍼
			ny = pos.first + dy[dir];
			ny = ny + dy[(dir - 1 + 4) % 4];
			nx = pos.second + dx[dir];
			nx = nx + dx[(dir - 1 + 4) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += ten;
			}
			ny = pos.first + dy[dir];
			ny = ny + dy[(dir + 1) % 4];
			nx = pos.second + dx[dir];
			nx = nx + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += ten;
			}

			// 7퍼
			ny = pos.first + dy[(dir - 1 + 4) % 4];
			nx = pos.second + dx[(dir - 1 + 4) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += seven;
			}
			ny = pos.first + dy[(dir + 1) % 4];
			nx = pos.second + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += seven;
			}

			// 5퍼
			ny = pos.first + dy[dir] * 2;
			nx = pos.second + dx[dir] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += five;
			}

			// 2퍼
			ny = pos.first + dy[(dir - 1 + 4) % 4] * 2;
			nx = pos.second + dx[(dir - 1 + 4) % 4] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += two;
			}
			ny = pos.first + dy[(dir + 1) % 4] * 2;
			nx = pos.second + dx[(dir + 1) % 4] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += two;
			}

			// 1퍼
			ny = pos.first + dy[(dir + 2) % 4];
			nx = pos.second + dx[(dir + 2) % 4];
			ny = ny + dy[(dir - 1 + 4) % 4];
			nx = nx + dx[(dir - 1 + 4) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += one;
			}
			ny = pos.first + dy[(dir + 2) % 4];
			nx = pos.second + dx[(dir + 2) % 4];
			ny = ny + dy[(dir + 1) % 4];
			nx = nx + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += one;
			}
		}

		dir = (dir + 1) % 4;

		for (int i = 0; i < idx; ++i)
		{
			if (pos.first == 1 && pos.second == 1)
				break;

			int nextY = pos.first + dy[dir];
			pos.first = nextY;
			int nextX = pos.second + dx[dir];
			pos.second = nextX;

			total = board[pos.first][pos.second];
			ten = total * 10 / 100;
			seven = total * 7 / 100;
			five = total * 5 / 100;
			two = total * 2 / 100;
			one = total * 1 / 100;
			alpa = total - (2 * ten + 2 * seven + 1 * five + 2 * two + 2 * one);
			board[pos.first][pos.second] = 0;

			// 알파 더해주기
			ny = pos.first + dy[dir];
			nx = pos.second + dx[dir];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += alpa;
			}

			// 10퍼
			ny = pos.first + dy[dir];
			ny = ny + dy[(dir - 1 + 4) % 4];
			nx = pos.second + dx[dir];
			nx = nx + dx[(dir - 1 + 4) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += ten;
			}
			ny = pos.first + dy[dir];
			ny = ny + dy[(dir + 1) % 4];
			nx = pos.second + dx[dir];
			nx = nx + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += ten;
			}

			// 7퍼
			ny = pos.first + dy[(dir - 1 + 4) % 4];
			nx = pos.second + dx[(dir - 1 + 4) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += seven;
			}
			ny = pos.first + dy[(dir + 1) % 4];
			nx = pos.second + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += seven;
			}

			// 5퍼
			ny = pos.first + dy[dir] * 2;
			nx = pos.second + dx[dir] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += five;
			}

			// 2퍼
			ny = pos.first + dy[(dir - 1 + 4) % 4] * 2;
			nx = pos.second + dx[(dir - 1 + 4) % 4] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += two;
			}
			ny = pos.first + dy[(dir + 1) % 4] * 2;
			nx = pos.second + dx[(dir + 1) % 4] * 2;
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += two;
			}

			// 1퍼
			ny = pos.first + dy[(dir + 2) % 4];
			nx = pos.second + dx[(dir + 2) % 4];
			ny = ny + dy[(dir - 1) % 4];
			nx = nx + dx[(dir - 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += one;
			}
			ny = pos.first + dy[(dir + 2) % 4];
			nx = pos.second + dx[(dir + 2) % 4];
			ny = ny + dy[(dir + 1) % 4];
			nx = nx + dx[(dir + 1) % 4];
			if (ny >= 1 && nx >= 1 && ny <= n && nx <= n)
			{
				board[ny][nx] += one;
			}
		}
		
		idx++;
		dir = (dir + 1) % 4;

	}
}

void solve()
{
	cin >> n;
	board = vector<vector<int>>(n + 1, vector<int>(n + 1));
	int init_total = 0;
	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			cin >> board[y][x];
			init_total += board[y][x];
		}
	}

	move();

	int cur_total = 0, ret = 0;
	for (int y = 1; y <= n; ++y)
	{
		for (int x = 1; x <= n; ++x)
		{
			cur_total += board[y][x];
		}
	}

	ret = init_total - cur_total;
	cout << ret;
}

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;
}

Twitter Facebook LinkedIn

BOJ 20057. 마법사 상어와 토네이도

🙇‍♀️[Gold III] 마법사 상어와 토네이도 - 20057

성능 요약

분류

제출 일자

문제 설명

입력

출력

🚀풀이

🚀코드

공유하기

참고

BOJ 1436. 영화감독 숌

배열 회전

Split 구현

최대공약수 최소공배수