본문 바로가기

알고리즘/백준56

[백준 11559] Puyo Puyo (C++) A. 문제설명 https://www.acmicpc.net/problem/11559 문제에 대한 자세한 설명은 링크 참조 1. 12*6 푸요푸요 게임판이 주어짐 2. 필드에 R/G/B/Y 뿌요를 놓음. 뿌요는 중력의 영향을 받아 아래에 바닥이나 다른 뿌요가 나올 때까지 아래로 떨어짐 3. 같은 색 뿌요가 4개 이상 상하좌우로 연결되어 있으면 연결된 같은 색 뿌요들이 한꺼번에 없어짐 4. 뿌요들이 없어지고 나서 위에 다른 뿌요들이 있다면, 역시 중력의 영향을 받아 차례대로 아래로 떨어짐 5. 아래로 떨어지고 나서 다시 같은 색의 뿌요들이 4개 이상 모이게 되면 또 터지고 연쇄 작용이 일어남 6. 상대방의 필드가 주어졌을 때, 몇 연쇄가 일어날 지 예측할 것 B. 접근법 BFS 1. 푸요푸요의 연쇄작용 계산 .. 2020. 8. 16.
[백준 19236] 청소년 상어 (C++) A. 문제설명 https://www.acmicpc.net/problem/19236 문제에 대한 자세한 설명은 링크 참조 1. 4*4 배열공간에 물고기의 번호와 방향이 각각 주어짐 2. 물고기의 방향은 1~8로, 12시방향부터 45도씩 반시계방향으로 각각 회전하여 주어짐 3. 이 배열공간 안 (0,0) 위치에 상어가 들어가 사냥을 시작 4. 상어는 (0,0) 위치의 물고기를 먹고 해당 물고기의 방향을 가짐 5. 이후 번호 순서대로 물고기가 이동, 물고기는 한 칸을 이동할 수 있고, 이동할 수 있는 칸은 빈 칸과 다른 물고기가 있는 칸이다. 현재 방향에서 이동하지 못할 경우 반시계방향으로 45도씩 회전하며 이동할 공간을 찾음 6. 물고기의 이동이 끝나면 다시 상어가 이동, 상어는 방향에 있는 칸으로 이동할 .. 2020. 8. 16.
[백준 17281] ⚾ (C++) A. 문제설명 https://www.acmicpc.net/problem/17281 문제에 대한 자세한 설명은 링크 참조 1. 9명으로 이루어진 야구팀의 선수들이 N이닝동안 플레이 2. 1번부터 9번의 타자들은 매 이닝마다 3아웃이 발생할 때까지 순환하며 타석에 들어감(1→2→3→...→8→9→1→2→...) 3. 각 타자가 타석에서 내는 결과는 아웃/안타/2루타/3루타/홈런로 아래와 같음 안타: 타자와 모든 주자가 한 루씩 진루 2루타: 타자와 모든 주자가 두 루씩 진루 3루타: 타자와 모든 주자가 세 루씩 진루 홈런: 타자와 모든 주자가 홈까지 진루 아웃: 모든 주자는 진루하지 못하고, 공격 팀에 아웃이 하나 증가 4. 매 이닝마다 타자가 수행할 결과는 정해짐 5. 감독은 1번 선수를 4번 타자로 선점.. 2020. 8. 6.
[백준 16985] Maaaaaaaaaze (C++) A. 문제설명 https://www.acmicpc.net/problem/16985 문제에 대한 자세한 설명은 링크 참조 1. 5*5 크기 판이 5개 주어짐 2. 각 판에는 들어갈 수 있는 칸과 들어갈 수 없는 칸이 구분됨 3. (0,0,0)에서 시작하여 (4,4,4)로 도착하는 경로 탐색 4. 각 판은 90도씩 360도 시계/반시계 방향으로 전부 돌릴 수 있으나 뒤집는 것은 허용되지 않음 5. 회전을 완료한 후, 5개의 판을 쌓음. 이 때 판을 쌓는 조합은 바뀌어도 됨 6. 모든 경우를 탐사해보아도 끝점에 도달불가한 경우 -1 출력, 끝점에 도달 가능한 경우 최적의 경로를 구하라 B. 접근법 DFS(조합구하기) + BFS(경로탐색) 먼저 문제의 조건들을 정리하면 5*5*5의 3차원 정육면체의 공간에서 (.. 2020. 8. 6.
[백준 17135] 캐슬 디펜스 (C++) A. 문제설명 https://www.acmicpc.net/problem/17135 문제에 대한 자세한 설명은 링크 참조 1. N*M 크기의 땅이 주어짐 2. 각 배열 안에는 적들이 위치하여 한턴마다 아래로 내려옴 3. 궁수 3명이 N+1번째 행에 위치하여 성을 지킴 3. 궁수들은 주어진 사정범위 D안에 들어온 적 중, 가장 가까운 적, 만약 가장 가까운 적이 여럿이라면 그 중에 가장 좌측의 적을 공격 4. 매 턴마다 적들이 내려오고 궁수들은 적을 공격하며 배열내 적들이 모두 내려올 때까지 반복 5. 궁수들이 위치하는 경우 중 최대로 적을 많이 죽일 수 있는 수를 구하라 B. 접근법 DFS + 시뮬레이션 우선, 궁수들이 성벽에 배치되는 경우에 대해서 중복되지 않도록 DFS로 모든 경우를 구해준다. 그리고,.. 2020. 7. 31.
[백준 17070] 파이프 옮기기 1 (C++) A. 문제설명 https://www.acmicpc.net/problem/17070 문제에 대한 자세한 설명은 링크 참조 1. N*N 크기의 땅이 주어짐 2. 위와 같은 파이프를 좌표 (N, N)까지 미는데, 미는 중간에 벽지가 있으면 안됨 3. 또한, 파이프는 밀면서 회전시킬 수 있고, 그 방향은 가로/세로/대각선임 4. 가로는 우측, 우하향만, 세로는 하향, 우하향만, 대각선은 우측, 하향, 우하향 모두 밀 수 있음 5. 파이프를 한쪽 끝에서 반대쪽 끝까지 밀 수 있는 모든 경우 구하기 B. 접근법 DFS 파이프의 방향별 미는 규칙에 따라 해당 밀 위치에 벽지가 있는지 확인하고, 없는 경우에만 깊이 우선탐색을 하도록 함 C. 풀이 1. 좌측 상단 모서리에서부터 탐색 진행 2. 나의 경우, 파이프가 회전.. 2020. 7. 28.
[백준 14890] 경사로 (C++) A. 문제설명 https://www.acmicpc.net/problem/14890 문제에 대한 자세한 설명은 링크 참조 1. N*N 크기의 땅이 각각 높이가 다른 땅이 주어짐 2. 각각의 칸마다, 높이 1씩 차이나는 땅에 대해 경사로를 설치하려 함 3. 설치 조건은 아래와 같다. 3-1. 경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다. 3-2. 낮은 칸과 높은 칸의 높이 차이는 1이어야 한다. 3-3. 경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다. 4. 주어진 땅에서 경사로를 놓아 길을 만들 수 있는 경우를 모두 구하라 B. 접근법 시뮬레이션 N*N 크기의 땅을 N행 + N열의 각각의 1차원 배열로 잘라내어 1차원 배열에 대해 .. 2020. 7. 16.
[백준 14503] 로봇 청소기 (C++) A. 문제설명 https://www.acmicpc.net/problem/14503 문제에 대한 자세한 설명은 링크 참조 1. 로봇 청소기가 방 안을 청소 2. 방은 N*M 크기의 배열로 되어있으며 벽이 있는 공간은 청소할 수 없음 3. 로봇청소기는 먼저 현재 위치를 청소하고 3-1. 왼쪽 방향에 아직 청소하지 않은 공간이 존재한다면, 그 방향으로 회전한 다음 한 칸을 전진 3-2. 왼쪽 방향에 청소할 공간이 없다면, 그 방향으로 회전 3-3. 네 방향 모두 청소가 이미 되어있거나 벽인 경우에는, 바라보는 방향을 유지한 채로 한 칸 후진 3-4. 네 방향 모두 청소가 이미 되어있거나 벽이면서, 뒤쪽 방향이 벽이라 후진도 할 수 없는 경우에는 작동을 멈춤 4. 최종적으로 청소기가 동작을 멈출 때, 청소한 칸.. 2020. 7. 7.
[백준 14501] 퇴사 (C++) A. 문제설명 https://www.acmicpc.net/problem/14501 문제에 대한 자세한 설명은 링크 참조 1. 퇴사전 남은 N일동안 최대한 많은 상담을 하려함 2. 상담시 걸리는 시간 Ti와 받는 보수 Pi가 각각 일별로 주어짐 3. 상담일의 일정을 적절히 배분하여 보수를 최대로 받을 수 있는 금액 구하기 B. 접근법 DFS + 시뮬레이션 N일의 일정동안 상담을 수행할지 말지에 대한 시리얼로 조합을 구하고 해당 조합을 완전탐색으로 시뮬레이션 한다. 그 중 최대가 되는 보수를 구하기 C. 풀이 1. 모든 조합을 만듬 2^15개 최대 2. for 모든 조합에 대한 시뮬레이션 수행, 그러나 불가능하면(일정 겹치거나, 안끝나는 것) 중간 종료 3. 매 시뮬레이션이 끝날 때, 수행 값의 최대를 업데.. 2020. 6. 16.
[백준 17143] 낚시왕 (C++) A. 문제설명 https://www.acmicpc.net/problem/17143 문제에 대한 자세한 설명은 링크 참조 1. 크기가 R*C인 지도가 존재 2. 해당 지도 위 각 칸에 상어가 존재하는데, 각각의 상어는 크기/방향/속력 정보를 가짐 3. 낚시왕은 처음 1열에 위치해있다가 오른쪽으로 한칸씩 이동하며 해당 열의 가장 상단의 상어를 잡는다. 4. 낚시 후 상어들이 현재 위치에서 주어진 방향으로 속도만큼 이동하는데, 여기서 벽을 만나면 방향은 반대로 바꾸고 속력을 유지한채로 이동한다. 5. 낚시왕이 끝열까지 이동하면서 잡을 수 있는 상어의 크기의 합 구하기 B. 접근법 시뮬레이션 낚시왕이 1~C 행까지 이동할 동안 상어의 이동 시뮬레이션 함수를 구현하여 움직임을 모사한다. 여기서 까다로운 점은 상어.. 2020. 6. 7.
[백준 12100] 2048 (Easy) (C++) A. 문제설명 https://www.acmicpc.net/problem/12100 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. 해당 지도 위에서 2048 게임을 수행 3. 기본적인 규칙은 상하좌우로 이동하며 같은 수는 병합되고 해당 이동 위치로 도형들이 달라붙는 것 4. 한번의 이동에서는 한번의 병합만 이루어지며 같은 수의 도형이 3개일 경우 병합의 우선순위는 해당 방향에 가까운 쪽부터 병합 5. 최대 다섯번 이동해서 나올 수 있는 가장 큰 수 구하기 B. 접근법 DFS + 시뮬레이션 먼저 DFS로 상하좌우의 이동 조합을 모두 구하고, 구해진 해당 이동 조합으로 도형 이동 시뮬레이션 수행 C. 풀이 1. 먼저 DFS로 상하좌우의 이동 조합을 모두 구함 2. 구해진 해당 이.. 2020. 6. 2.
[백준 3190] 뱀 (C++) A. 문제설명 https://www.acmicpc.net/problem/3190 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×N인 지도가 존재 2. 뱀은 (0, 0) 좌표에서 우측으로 이동시작하는데, 아래와 같은 규칙으로 이동 2-1. 먼저 뱀은 몸길이를 늘려 머리를 다음칸에 위치 2-2. 만약 이동한 칸에 사과가 있다면, 그 칸에 있던 사과가 없어지고 꼬리는 움직이지 않음 2-3. 만약 이동한 칸에 사과가 없다면, 몸길이를 줄여서 꼬리가 위치한 칸을 비워줌 3. 수초가 지났을 때 입력으로 들어온 방향전환 명령에 따라 방향을 전환 4. 뱀이 벽이나 자기자신에 부딫히면 종료 5. 마지막으로 종료된 시간 반환 B. 접근법 시뮬레이션 Dummy 게임에 대한 시뮬레이션을 충실히 구현하자. 뱀의 좌표에 .. 2020. 5. 27.
[백준 14499] 주사위 굴리기 (C++) A. 문제설명 https://www.acmicpc.net/problem/14499 문제에 대한 자세한 설명은 링크 참조 1. 크기가 N×M인 지도가 존재 2. 지도 위에 주사위의 위치가 주어지고, 주사위는 입력에 따라 동서남북으로 이동 3-1. 이동한 칸에 쓰여 있는 수가 0이면, 주사위의 바닥면에 쓰여 있는 수가 칸에 복사 3-2. 이동한 칸에 쓰여 있는 수가 0이 아니면, 칸에 쓰여 있는 수가 주사위의 바닥면으로 복사되며, 칸에 쓰여 있는 수는 0이 됨 4. 주사위가 이동했을 때 마다 상단에 쓰여 있는 값 출력하기 B. 접근법 시뮬레이션 간단한 시뮬레이션 유형의 문제, 주어진 입력에 따라 주사위를 동서남북으로 굴리는 함수를 따로 구현하였다. 남/북으로 이동시 3/4면이 고정되고 나머지 면이 이동, 동.. 2020. 5. 18.
[백준 16236] 아기 상어 (C++) A. 문제설명 https://www.acmicpc.net/problem/16236 문제에 대한 자세한 설명은 링크 참조 1. N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 존재 2. 처음에 아기 상어의 크기는 2이고, 아기 상어는 1초에 상하좌우로 인접한 한 칸씩 이동 3. 아기 상어는 자신의 크기보다 작은 물고기만 먹을 수 있고 크기가 같은 물고기는 먹을 수 없지만, 그 물고기가 있는 칸은 지나갈 수 있음 4. 먹을 수 있는 물고기가 여러마리라면 거리 -> Y축 좌표 -> X축 좌표 기준으로 우선순위에 따라 선택 5. 물고기 다 먹고 먹을 게 없는 상황에서 걸린 시간 반환 B. 접근법 BFS + 정렬 처음에 시뮬레이션으로 풀어보려다가 실패 후 BFS + 정렬로 다시 풀게 되었다. BFS는 상.. 2020. 5. 15.
[백준 14888] 연산자 끼워넣기 (C++) A. 문제설명 https://www.acmicpc.net/problem/14888 문제에 대한 자세한 설명은 링크 참조 1. N개의 수가 주어지고 그 사이에 N-1개의 연산자를 넣으려고 함 2. N개의 수에 대한 연산자의 조합은 다음과 같이 삽입될 수 있다. 1+2+3-4×5÷6 1÷2+3+4-5×6 1+2÷3×4-5+6 1÷2×3-4+5+6 3. N-1개의 연산자는 +, -, ×, ÷로 각각 사용할 수 있는 수가 주어짐 4. 연산식 조합 중 최대와 최소를 만드는 것을 구하면 됨 * (중요) 여기서 연산자 우선순위는 무시되고, 연산식은 좌에서 우의 순서로 계산되면 된다. B. 접근법 DFS 주어진 연산자 갯수들을 이용하여 각 연산자들의 배치 조합을 DFS로 모두 만들고, 해당 연산식 중 최대와 최소를 업.. 2020. 5. 8.

티스토리툴바