백준
BaekJoon(10989)::수 정렬하기 3
문제 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제파악 오름차순 정렬 수의 개수가 최대 10,000,000개 → 시간초과 주의 수의 범위가 10,000보다 작기 때문에 'Counting Sort' 선택 문제풀이 'Counting Sort'를 이해하고 알고 있다면 쉽게 풀수 있는 문제이다. 나올수 있는 수의 범위가 작다 수의 범위가 자연수로 한정되어 있다. #include #define _CRT_SECURE_NO_WARNINGS using namespace std; int main() { short arr[10001] = ..
BaekJoon(2798)::블랙잭
문제 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장 www.acmicpc.net 문제파악 주어진 N개의 카드에서 3장을 선택하여, 더한 값이 M의 값보다 작으면서 최대값 N개에서 3개를 고른다 → $ _{n} \mathrm{C}_{3} $ M보다 작으면서 최대값의 조건을 만족하는지 확인 문제풀이 이 경우는 단순 완전탐색을 선택하였다. 이유는 문제의 사이즈가 그렇게 크지 않았기 때문이다. $ _{n} \mathrm{C}_{3} $ 에서 n이 500이라면 $500 \times 499 \times 498 = ..
BaekJoon(11729)::하노이의 탑 이동 순서
문제 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 문제파악 하노이 탑의 이동 원리 파악 → 출력 하노이 탑의 이동 횟수 → 재귀식을 일반항으로 도출하여 주워진 판의 갯수를 통해 총 이동횟수를 알 수 있다. 문제풀이 하노이 탑의 이동횟수 → $a_n = 2^n-1$ 각 하노이의 마지막 판의 이동을 출력 #include #include using namespace std; void hanoi(int n, int from, int via, int to) { if (n == 1) { printf("%d..
BaekJoon(10872)::팩토리얼
문제 10872번: 팩토리얼 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제파악 팩토리얼 → $n! = 1 \times 2 \times · · · \times n $ 문제풀이 재귀 이용 : $factorial(n)$ → $n \times factorial(n-1)$ #include using namespace std; int factorial(int n) { if (n == 1 || n == 0) return 1; return n * factorial(n - 1); } int main() { int n; cin >> n; cout > n; for(int i = 1; i
BaekJoon(1002)::터렛
문제 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 문제파악 각 터렛에서 근무하는 직원에서 적까지의 거리가 주어짐 → 적이 위치할수 있는 위치는 원이 된다. 즉, 근무하는 직원은 원의 중심, 적의 위치는 원 위에 존재한다. 적이 있을 수 있는 위치는 두 원의 위치관계에 의하여 해결 될 수 있다. 문제풀이 두 원의 위치관계를 조건으로 문제를 해결할 수 있다. 동심원인 경우 완전 동일한 원일 경우 다른 원일 경우 동심원이 아닌 경우 접할경우 두점에서 만날 경우 만나지 않는 경우 #include using namespace std; int main() { int t..
BaekJoon(3053)::택시 기하학
문제 3053번: 택시 기하학 첫째 줄에는 유클리드 기하학에서 반지름이 R인 원의 넓이를, 둘째 줄에는 택시 기하학에서 반지름이 R인 원의 넓이를 출력한다. 정답과의 오차는 0.0001까지 허용한다. www.acmicpc.net 문제파악 택시기하학에 대한 내용 공부 기존 유클리드 기하학과 다른 택시기하학에서의 원의 넓이를 출력 문제풀이 #include #define _USE_MATH_DEFINES #include "math.h" using namespace std; int main(void) { int r; cin >> r; cout
BaekJoon(9020)::골드바흐의 추측
문제 9020번: 골드바흐의 추측 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아 www.acmicpc.net 문제 파악 해당 문제는 제목에서도 말하듯이 골드바흐의 추측을 통해 해결할 수 있다. 골드바흐의 추측은 2보다 큰 짝수는 두소수의 합으로 나타낼수 있다는 추측으로 해당 수를 골드바흐 수라고 한다. 주어진 골드바흐의 수는 두 소수의 합들로 나타낼 수 있다. 여러 소수쌍중 해당 값의 차이가 가장 작은 것을 출력한다. 위 정리에서 알 수 있듯 우선 소수판별을 위해 에라테토스테네스의 체를 먼저 작성한다. 문제풀이 #include #include ..
BaekJoon(1850)::최대공약수
문제 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 문제 파악 : 1로 이루어진 수의 최대공약수는 두 수의 길이의 최대공약수가 해당 공약수의 길이가 되며 그 공약수 또한 1로 이루어지게 된다. : 왜냐하면 두 수는 1로 이루어져 있기 때문에 위와 같은 이해가 만들어진다. 예시 1, 11, 111, 1111 → 1 11, 1111, 111111 → 11, 1111 문제풀이 : 두 수의 길이의 최대공약수를 구하면 그 값이 주어진 두수의 최대공약수의 길이가 된다. #include #inclu..
BaekJoon(1085)::직사각형에서 탈출
문제 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형의 왼쪽 아래 꼭짓점은 (0, 0)에 있고, 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램을 작성하시오. www.acmicpc.net 문제파악 사각형 내부에 x,y가 주어짐(조건 참고) 벽면에 가장 가까운 거리를 찾으면 된다(최소값) 문제풀이 위 그림의 h-y, w-x, x, y의 값 중 최소값을 구해주면 된다 #include using namespace std; int main() { int x, y, w, h; cin >> x >> y >> w >> h; int min = x; if (min > y) min = y; if (min > w - x) min = w - x; i..
BaekJoon(2869)::달팽이는 올라가고 싶다
문제 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B > a >> b >> v; ..