프로그래밍 공부 노트

https://www.acmicpc.net/problem/14499 14499번: 주사위 굴리기 첫째 줄에 지도의 세로 크기 N, 가로 크기 M (1 ≤ N, M ≤ 20), 주사위를 놓은 곳의 좌표 x, y(0 ≤ x ≤ N-1, 0 ≤ y ≤ M-1), 그리고 명령의 개수 K (1 ≤ K ≤ 1,000)가 주어진다. 둘째 줄부터 N개의 줄에 지 www.acmicpc.net 특별한 알고리즘을 사용하지 않는 구현 문제이다. 주사위를 객체로 만든 뒤 주사위의 회전을 메소드로 구현하면 쉽게 풀 수 있다. #include #define MAX_N 20 // N: 지도의 세로 크기, M: 지도의 가로 크기 int N, M; // 좌표 class coord { public: // (x, y): (가로, 세로) i..

https://www.acmicpc.net/problem/15653 15653번: 구슬 탈출 4 첫 번째 줄에는 보드의 세로, 가로 크기를 의미하는 두 정수 N, M (3 ≤ N, M ≤ 10)이 주어진다. 다음 N개의 줄에 보드의 모양을 나타내는 길이 M의 문자열이 주어진다. 이 문자열은 '.', '#', 'O', 'R', 'B' www.acmicpc.net 기본적으로 문제 자체는 구슬 탈출 2와 같은 문제이다. 단 이 문제는 기울일 수 있는 최대 횟수가 정해져 있지 않으므로, 각 상태에 도달할 수 있는 최소 기울임 횟수를 따로 저장하여 중복되는 경우의 수를 최대한 쳐내야 한다. #include typedef unsigned int ui; #define MAX_N 10 #define INF 0xffff..

https://www.acmicpc.net/problem/20327 20327번: 배열 돌리기 6 크기가 2N×2N인 배열이 있을 때, 배열에 연산을 R번 적용하려고 한다. 연산은 8가지가 있고, 연산에는 단계 ℓ (0 ≤ ℓ < N)이 있다. 단계 ℓ은 배열을 부분 배열로 나눌때 사용하는 값이며, 부분 www.acmicpc.net 철저한 구현 문제이다. 배열의 각 성분마다 돌린 후의 위치를 계산하여 배열을 돌린 각 결과를 저장한 뒤, 배열을 모두 돌린 후의 결과를 출력하면 된다. #include #define MAX_N 7 #define pow(i) (1

https://www.acmicpc.net/problem/20005 20005번: 보스몬스터 전리품 입력의 첫째 줄에는 멤멤월드의 지도의 크기를 나타내는 두 정수 M(6 ≤ M ≤ 1000), N(6 ≤ N ≤ 1000)과 플레이어의 수 P(1 ≤ P ≤ 26)가 주어진다. M은 지도의 세로 길이, N은 지도의 가로 길이이다. 입 www.acmicpc.net 철저한 구현 문제이다. 각 플레이어가 보스가 있는 장소까지 1초에 한 칸씩 이동한 뒤 1초에 한 번씩 dps만큼의 데미지를 넣는 문제인데, 특별한 알고리즘이 사용되는 것이 아니므로 HP가 양수일 동안 루프하며 각 플레이어의 이동 및 데미지 계산을 진행하면 된다. #include #include #include using namespace std; t..

https://www.acmicpc.net/problem/23350 23350번: K 물류창고 K사의 물류창고를 운영하는 도커 씨는 오늘 발주를 처리하기 위해 N 개의 컨테이너들을 적재해야 한다. 도커씨는 이 일을 하나의 로봇을 이용해 처리하려 한다. 로봇은 컨테이너를 옮길 때마다 www.acmicpc.net 모든 컨테이너를 컨테이너의 큐 q1에 넣은 뒤, O(n ^ 2)의 시간에 걸쳐 다른 큐 q2에 우선순위의 오름차순으로 정렬되게 넣는다. 그 다음 q2의 모든 컨테이너를 컨테이너의 스택 s1에 넣는데, 이 때 우선순위가 같으면서 무게가 무거운 컨테이너를 스택에 넣을 경우 우선순위가 같으면서 더 가벼운 컨테이너를 컨테이너의 스택 s2에 임시로 넣은 뒤 q2의 컨테이너를 s1에 놓고, 다시 s2의 컨테이..

https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 특별한 알고리즘 없이 주어진 규칙을 제대로 구현해야 한다. #include #include using namespace std; typedef pair coord; typedef pair dust; #define MAX_R 50 #define _y first #define _x second #define _coord first #define _amount second // R, C: 방의 크기,..

https://www.acmicpc.net/problem/16236 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 1×1 크기의 공간을 노드로, 상하좌우로 인접한 칸 사이의 관계를 에지로 보면 이 문제는 상어의 좌표에서 먹을 수 있는 물고기의 좌표까지 bfs를 여러 번 실행하는 문제이다. 이 때 먹을 수 있는 물고기를 발견한 경우, bfs를 종료하지 않고 같은 거리에 있는 모든 좌표를 탐색해야 한다. #include #include #include using namespace std; #define M..

https://www.acmicpc.net/problem/12100 12100번: 2048 (Easy) 첫째 줄에 보드의 크기 N (1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 게임판의 초기 상태가 주어진다. 0은 빈 칸을 나타내며, 이외의 값은 모두 블록을 나타낸다. 블록에 쓰여 있는 수는 2 www.acmicpc.net 보드의 각 상태를 클래스의 형태로 저장한 뒤, 보드를 5회 이동시켜 얻을 수 있는 모든 상태를 탐색해야 한다. 이 때 가능한 블록의 최댓값은 초기 상태의 최댓값 혹은 블록이 합쳐져서 만들어진 블록의 최댓값이므로, 최댓값 계산은 보드의 초기 상태를 입력받을 때와 블록이 합쳐질 때만 실행하면 된다. #include #define MAX_N 20 #define init(i,..

https://www.acmicpc.net/problem/8911 8911번: 거북이 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 컨트롤 프로그램이 주어진다. 프로그램은 항상 문제의 설명에 나와있는 네가지 명령으로만 이루어져 www.acmicpc.net 거북이가 지나간 영역을 모두 포함하는 직사각형은 거북이가 존재했던 모든 점을 포함한다. 따라서 거북이가 존재했던 좌표를 추적하면서, 거북이의 x, y의 최솟값과 최댓값을 계산한 뒤, (y의 최댓값 - y의 최솟값) * (x의 최댓값 - x의 최솟값)을 출력하면 정답이 된다. #include #include using namespace std; typedef pair coord; #define _y first..

https://www.acmicpc.net/problem/4600 4600번: 정글의 법칙 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 음수 -B와 양수 P가 주어진다. B는 다리의 수이고, P는 사람의 수이다. B와 P는 20을 넘지 않는다. (B가 음수로 주 www.acmicpc.net 각 나무에서 다리를 지나가는 사람과 다리가 비면 지나갈 사람 두 종류로 나누자. while문으로 무한 반복을 시키면서, 빈 다리가 있는 지역에 다리가 비었을 때 지나갈 사람이 있을 경우, 가능한 한 많은 사람을 다리에 넣은 뒤 일정 시간이 지나면 다리를 건넌 것으로 간주한다. 또 아직 사람이 건너고 있는 다리가 있는 경우, 반복문을 통해 여러 번 접근할 것이므로 시간을 1 감소한 ..