문제 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 풀이 유클리드 호제법, 수학 완전 탐색으로 하면 시간초과가 발생한다. 주어진 정수 A를 M으로 나눈 나머지가 R이라면 다음을 만족한다. R = A - (A / M) * M 여기서 A는 배열로 주이지므로 다음이 만족한다. R = A[0] - (A[0] / M) * M R = A[1] - (A[1] / M) * M ... R = A[N - 1] - (A[N - 1] / M) * M 문제에서 R이 같은 값이므로 다음이 만족한다. A[1] - A[0] = (A[1] / M - A..
문제 17087번: 숨바꼭질 6 수빈이는 동생 N명과 숨바꼭질을 하고 있다. 수빈이는 현재 점 S에 있고, 동생은 A1, A2, ..., AN에 있다. 수빈이는 걸어서 이동을 할 수 있다. 수빈이의 위치가 X일때 걷는다면 1초 후에 X+D나 X-D로 이 www.acmicpc.net 풀이 유클리드 호제법 S에서 일정한 간격으로 이동할 때, 모든 A에 도달해야 한다. 즉, 간격이 모든 A와의 차이의 공약수여야만 한다. 이 간격 중 최댓값이므로, 최대공약수가 정답이다. 코드 #include using namespace std; vector diffs; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % ..
문제 2485번: 가로수 첫째 줄에는 이미 심어져 있는 가로수의 수를 나타내는 하나의 정수 N이 주어진다(3 ≤ N ≤ 100,000). 둘째 줄부터 N개의 줄에는 각 줄마다 심어져 있는 가로수의 위치가 양의 정수로 주어지며, 가 www.acmicpc.net 풀이 유클리드 호제법 모든 나무를 같은 간격으로 심으려면, 현재 심어져 있는 가로수 사이의 간격의 최소공배수만큼을 간격으로 설정하고 심으면 된다. // 가로수 사이의 간격의 최소공배수를 구한다. int GCD = nums[1] - nums[0]; for (int i = 1; i < nums.size() - 1; ++i) { GCD = gcd(GCD, nums[i + 1] - nums[i]); } 첫 가로수와 마지막 가로수 사이의 거리를 range라고..
문제 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 풀이 유클리드 호제법 회전하는 바퀴는 반지름 / (첫 번째 링과 i 번째 링의 반지름의 gcd) 로 구할 수 있다. 코드 #include using namespace std; int nums[100]; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } int main() { ios_base::sync_with_stdio(0..
유저 인터페이스와 HUD 메뉴와 HUD 같은 유저 인터페이스를 만드는 아티스트와 프로그래머를 위한 정보와 안내서입니다. docs.unrealengine.com HUD(Heads-up Display)는 플레이어에게 게임에 대한 정보를 표시해 주기도 하고, 가끔 플레이어와의 상호작용도 한다. HUD는 게임의 계기판의 역할을 하며 정보를 보여주는데, 플레이어에게 점수, 생명력, 남은 시간 등 게임의 현재 상태를 알리는 역할을 한다. 유저 인터페이스와 달리 보통은 상호작용을 위한 요소는 아니다. 즉, 플레이어는 HUD를 클릭할 수 없다는 뜻으로, 정보를 알려주는 게임 인터페이스는 HUD로 설정해야 한다고 볼 수 있다. HUD는 GameMode에서 설정할 수 있다. 유저 인터페이스처럼, 플레이어 컨트롤러나 다른 ..
문제 풀이 유클리드 호제법 간단한 유클리드 호제법 문제이다. 아래는 a, b의 최대공약수를 반환하는 유클리드 호제법 함수이다. int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b = temp; } return a; } 문제에서 주어진 분수를 먼저 통분하여 합을 계산한다. 합한 분자와 분모의 최대공약수를 구하여 각각에 나누면 기약 분수가 된다. 코드 #include using namespace std; int gcd(int a, int b) { if (a < b) { swap(a, b); } int temp; while (b != 0) { temp = a % b; a = b; b..
문제 14891번: 톱니바퀴 총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여져 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴 www.acmicpc.net 풀이 구현, 시뮬레이션 현재 order에서 움직일 기어들을 찾아서 방향에 맞게 회전시켜야 한다. 현재 order 기어의 오른쪽 기어들과 왼쪽 기어들을 나눠서 생각한다. // 현재 기어의 오른쪽 기어들 탐색 for (int current_gear = order_gear + 1; current_gear < 4; ++current_gear) { // 현재 기어와 현재 기어 바로 왼쪽 기어의 상태를 비교 if (gear[current_gear - 1][2] !=..
문제 16234번: 인구 이동 N×N크기의 땅이 있고, 땅은 1×1개의 칸으로 나누어져 있다. 각각의 땅에는 나라가 하나씩 존재하며, r행 c열에 있는 나라에는 A[r][c]명이 살고 있다. 인접한 나라 사이에는 국경선이 존재한다. 모 www.acmicpc.net 풀이 구현, 시뮬레이션, 너비 우선 탐색 각 칸에 대해서 연합을 이룰 수 있는지 확인하기 위해, 각 칸의 상하좌우를 탐색하여 연합을 만든다. 연합은 시작 칸과 인접한 칸에서만 이루어지는게 아니라, 연합이 이루어진 칸에서도 인접한 칸을 비교하여 조건에 맞으면 연합이 이루어진다. 그러므로 각 칸을 bfs로 탐색하면서 연합을 이루는 칸이 어느 칸인지 탐색한다. 연합 벡터의 수가 2이상이라면, 인구 이동이 가능한 상태이므로 인구 이동을 실시한다. 이를..
문제 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 풀이 구현, 시뮬레이션 주사위의 각 면을 나눠서 생각하고, 현재 주사위의 아래쪽(D), 오른쪽(R), 앞쪽(F)에 해당하는 주사위 면을 설정하여 해결하였다. 각 면의 인덱스를 0, 1, 2, 3, 4, 5라고 하면 처음 상태에서 D는 0, R은 2, F는 4이다. 주사위를 4방향으로 움직이면 D, R, F는 밑의 코드처럼 변한다. // 주사위를 4방향으로 굴렸을 때, 아래, 오른쪽, 앞쪽의 주..
문제 17406번: 배열 돌리기 4 크기가 N×M 크기인 배열 A가 있을때, 배열 A의 값은 각 행에 있는 모든 수의 합 중 최솟값을 의미한다. 배열 A가 아래와 같은 경우 1행의 합은 6, 2행의 합은 4, 3행의 합은 15이다. 따라서, 배열 A의 www.acmicpc.net 풀이 구현, 브루트포스 알고리즘, 백트래킹 문제를 잘 읽어야 한다. 회전의 순서가 고정적인 것이 아니라, 배열의 최솟값을 구할 수 있도록 회전의 순서를 바꿀 수 있다. 회전의 순서를 정할 수 있도록, dfs를 이용하여 순열 알고리즘을 구현한다. // dfs를 이용한 순열 void dfs(bool select[], int map[], int cnt, int n, int k, vector v) { if (cnt == k) { sol..
