알고리즘/백준

문제 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..

문제 풀이 유클리드 호제법 간단한 유클리드 호제법 문제이다. 아래는 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..

문제 1941번: 소문난 칠공주 총 25명의 여학생들로 이루어진 여학생반은 5×5의 정사각형 격자 형태로 자리가 배치되었고, 얼마 지나지 않아 이다솜과 임도연이라는 두 학생이 두각을 나타내며 다른 학생들을 휘어잡기 시작 www.acmicpc.net 풀이 브루트포스 알고리즘, 너비 우선 탐색, 조합론, 백트래킹 학생은 전체 25명이다. 여기서 자리를 7개 선택하여 문제의 조건이 맞는지 확인하는 방식으로 답을 구한다. 학생의 수가 많지 않기 때문에 브루트포스로 구현해도 시간 초과는 발생하지 않는다. 자리를 선택하는 방법은 백트래킹을 사용한다. 자리 선택과 해제를 반복하며 자리를 7개 선택했다면 현재 상태가 문제의 조건을 만족하는지 확인한다. 문제의 조건은 다음과 같다. 선택한 자리 모두 상하좌우로 연결되어 ..

문제 10164번: 격자상의 경로 입력의 첫째 줄에는 격자의 행의 수와 열의 수를 나타내는 두 정수 N과 M(1 ≤ N, M ≤ 15), 그리고 ○로 표시된 칸의 번호를 나타내는 정수 K(K=0 또는 1 < K < N×M)가 차례로 주어지며, 각 값은 공백으 www.acmicpc.net 풀이 수학, 다이나믹 프로그래밍, 조합론 격자상에서 각 칸에 도달할 수 있는 경로의 경우의 수는 다음과 같다. 1 1 1 1 1 1 2 3 4 5 1 3 6 10 15 0번 행과 0번 열은 모두 한가지의 방법만 존재한다. (x, y) 칸에 도달할 수 있는 경로의 수는 (x - 1, y) 칸과 (x, y - 1) 칸에 올 수 있는 경우의 수의 합이다. 중간 경로 K를 지나면서 마지막 칸에 도달하는 경우의 수는 (1번 칸에서..