본문 바로가기

전체 글137

백준 g2 20061 모노미노도미노 2 c++ https://www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 문제 설명 빨강, 파랑, 초록으로 나뉘어진 특수한 보드가 있다. 빨간색 보드에 1*1, 2*1, 1*2인 블록을 놓을 수 있으며, 이는 파랑, 초록 보드에도 같이 놓여진다. 파랑, 초록에 놓여질 때는 슬라이딩 하듯이 놓을 수 있는 가장 끝에 놓아진다. 한 행/열에 4칸이 모두 차면, 그 줄은 사라지고 점수를 1점 얻는다. 해당 줄이 사라지면 그 위에 줄이 그대로 내려온다. 파랑, 초록 .. 2024. 1. 23.
백준 g1 4991 로봇 청소기 c++ https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 문제 설명 M, N 크기의 방에 *: 더러운 칸, x: 가구, o: 로봇 청소기의 시작 위치가 존재한다. 더러운 칸의 개수는 10개를 넘지 않으며, 방 크기는 최대 20*20이다. 로봇청소기 시작 위치에서 더러운 칸을 모두 깨끗한 칸으로 청소할 때, 이동횟수의 최솟값 구하기 방문했던 곳 다시 방문 가능 풀이 1. 먼지의 개수가 10개 이하이므로, 무슨 먼지부터 청소할 건지 정하는 순열(10!)을 구한다. .. 2024. 1. 23.
백준 g2 17825 주사위 윷놀이 c++ https://www.acmicpc.net/problem/17825 17825번: 주사위 윷놀이 주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 www.acmicpc.net 문제 설명 말은 시작 칸에 총 4개 파란색 칸에 멈추면, 파란색 화살표를 따라 가야 함 말이 이동을 마치는 칸(도착점)에 다른 말이 있으면 X 말이 이동을 마칠 때마다 칸에 적혀 있는 수가 점수로 추가됨 주사위에서 나올 수 10개가 주어질 때, 얻을 수 있는 점수의 최댓값 풀이 1.주사위 판 짜기 빨간 화살표만 따라갔을 때 경로 0, 10에 도착한 경우 경로 1, 20에 도착한 경우 경로 2, 3.. 2024. 1. 22.
백준 g2 17822 원판 돌리기 c++ https://www.acmicpc.net/problem/17822 17822번: 원판 돌리기 반지름이 1, 2, ..., N인 원판이 크기가 작아지는 순으로 바닥에 놓여있고, 원판의 중심은 모두 같다. 원판의 반지름이 i이면, 그 원판을 i번째 원판이라고 한다. 각각의 원판에는 M개의 정수가 적혀 www.acmicpc.net 문제 설명 1~N번의 원판에 M개의 숫자가 있다. T번, x배수의 원판을 d방향으로 k칸 만큼 돌릴 수 있다. 이때, 인접하면서 같은 수가 있으면 모두 지운다. 없는 경우에는 평균을 구한 다음 평균보다 큰 수는 +1, 작은 수는 -1 풀이 1. 원판 board[N][M]: 원판에 적혀있는 숫자들 정보, x배수를 써야하기 때문에 N은 1~N, M은 나머지 연산 쓰기 유용하도록 0~M.. 2024. 1. 22.
백준 g3 16986 인싸들의 가위바위보 c++ https://www.acmicpc.net/problem/16986 16986번: 인싸들의 가위바위보 두 사람이 같은 손동작을 내어 무승부가 발생할 경우 경기 진행 순서상 뒤인 사람이 이긴 것으로 간주함에 다시 한 번 유의한다. 구체적으로, 경기 진행 순서는 지우, 경희, 민호 순으로 고정되 www.acmicpc.net 헷갈릴 수 있는 요소 문제가 헷갈린다는 평이 많다. 그러니 문제를 읽고 나서 풀기 전에 꼭 예제 밑에 있는 노트를 읽어보자. 주어지는 경희, 민호의 손동작 순서는 라운드별이 아닌, 자신이 경기를 하나 참여할 때마다 하나씩 쓰는 것. ex. 지우vs경희, 경희vs 민우 경기를 차례대로 진행한다고 가정했을 때, 2번째 경기에서 민우는 자신의 두번째 손동작을 내는 것이 아니라, 첫 번째 손동작.. 2024. 1. 21.
백준 g1 17143 낚시왕 c++ https://www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 설명 낚시왕 오른쪽 한 칸 이동 같은 열 중 가장 가까운 상어 잡음 상어 이동 칸 넘으면 반대 방향 한 칸에 여러 상어 -> 가장 큰 상어만 살아남음 문제 풀이 중요한 것은 상어의 이동이다 1. 상어들이 벽 끝에 부딪혔을 때를 어떻게 한번에 계산해서 다음 위치를 정할 지 2. 상어를 옮기면서 먹으면, 이동해서 다른 곳에 가있어야 할 상어가 먹히는 경우가 있음. ex. 상어.. 2024. 1. 20.
백준 g1 13460 구슬 탈출 2 c++ https://www.acmicpc.net/problem/13460 13460번: 구슬 탈출 2 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 문제 설명 가장자리가 벽으로 막혀있는 판 안에 빨간 구슬 R, 파란 구슬 B, 빠져나가는 구멍 O 존재 판을 상하좌우로 기울여서 빨간 구슬 R을 구멍으로 빠져나가도록 해야 함 이때 파란 구슬 B가 구멍으로 나가거나, 빨간 구슬과 파란 구슬이 동시에 구멍에 빠져나가면 안 됨 풀이 1. 기울이기 방향 4가지로 움직일 수 있고, 최대 10번 이므로 4^.. 2024. 1. 19.
백준 g2 16985 Maaaaaaaaaze c++ https://www.acmicpc.net/problem/16985 16985번: Maaaaaaaaaze 첫째 줄부터 25줄에 걸쳐 판이 주어진다. 각 판은 5줄에 걸쳐 주어지며 각 줄에는 5개의 숫자가 빈칸을 사이에 두고 주어진다. 0은 참가자가 들어갈 수 없는 칸, 1은 참가자가 들어갈 수 있는 칸을 www.acmicpc.net 문제 설명 5*5 판이 5개 주어지고, 참가자가 들어갈 수 있는 칸과 그렇지 않은 칸이 각각 1, 0 으로 주어진다. 5개의 판을 순서 상관 없이 자유롭게 쌓을 수 있고, 각각 자유롭게 회전이 가능하다. (뒤집는 건 X) 맨 위 임의의 꼭짓점을 입구로 정하면, 그 반대쪽 아래에 있는 꼭짓점이 출구가 된다. 이렇게 완성된 5*5*5 미로를 탈출하는 최소거리를 구하는 것이 목표 .. 2024. 1. 18.
백준 g1 1799 비숍 c++ https://www.acmicpc.net/problem/1799 1799번: 비숍 첫째 줄에 체스판의 크기가 주어진다. 체스판의 크기는 10이하의 자연수이다. 둘째 줄부터 아래의 예와 같이 체스판의 각 칸에 비숍을 놓을 수 있는지 없는지에 대한 정보가 체스판 한 줄 단위로 www.acmicpc.net 시간초과 났던 이유 처음에는 해당 칸에 비숍을 놓냐 안 놓냐로 O(2^100)의 시간이 걸릴 거란 걸 알았지만, 딱히 다른 해결책이 떠오르지도 않고 1. 해당 칸에 놓을 수 있을지 없을지 N; for (int i = 0; i > board[i][j]; if (board[i][j] == 1) { if ((i + j) % 2 .. 2024. 1. 17.

티스토리툴바