본문 바로가기

알고리즘98

백준 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.
백준 g1 18809 Gaaaaaaaaaarden c++ https://www.acmicpc.net/problem/18809 18809번: Gaaaaaaaaaarden 첫째 줄에 정원의 행의 개수와 열의 개수를 나타내는 N(2 ≤ N ≤ 50)과 M(2 ≤ M ≤ 50), 그리고 초록색 배양액의 개수 G(1 ≤ G ≤ 5)와 빨간색 배양액의 개수 R(1 ≤ R ≤ 5)이 한 칸의 빈칸을 사이에 두 www.acmicpc.net 풀이 1. 큐 2개 동시에 돌리기 Red 배양액과 Green 배양액이 있는데, 둘이 서로에게 영향을 주므로 하나를 다 bfs 돌려놓고 다른 하나 마저 돌리기 이런 게 안 된다. 동시에 돌려야 한다. BFS는 거리가 1인 칸 모두 방문 -> 2인 칸 모두 방문 -> 3인 칸 모두 방문 ... 이렇게 거리순으로 방문을 하고, 거리가 1인 칸을.. 2024. 1. 17.
백준 g3 1941 소문난 칠공주 c++ https://www.acmicpc.net/problem/1941 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 DFS는 ㅜ자 형태의 경로가 안 된다. 전체 25자리 중 7자리를 고르는 25C7을 해도 충분히 시간 제한 안에 풀 수 있다. next_permutation을 통해 25C7를 구하고, Y의 개수가 4개를 넘거나 인접하지 않으면 continue 하도록 했다 서로 인접해있는지는 BFS로 풀었고, prin 한 명을 시작점으로 해서 area가 7이 되지 않으면 인접하지 않다는 뜻이므로 false를 re.. 2024. 1. 16.
백준 g5 16987 계란으로 계란치기 c++ https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 문제 설명 input 계란의 내구도, 계란의 무게 output 깰 수 있는 계란 개수의 최대 규칙 1. 맨 왼쪽의 계란을 든다. 2. 깰 수 있는 계란 중 하나를 골라 계란을 부딪힌다. 이때 들고 있는 계란이 깨져있거나, 깰 수 있는 계란이 남아있지 않을 땐 그냥 넘어간다. 3. 한 칸 오른쪽 계란을 들고, 2번을 반복한다. 4. 맨 오른쪽 계란까지 수행했으면 끝낸다. 풀이 N 0).. 2024. 1. 16.

티스토리툴바