D.JOUNG

문제 : https://www.acmicpc.net/problem/2023 2023번: 신기한 소수 수빈이가 세상에서 가장 좋아하는 것은 소수이고, 취미는 소수를 가지고 노는 것이다. 요즘 수빈이가 가장 관심있어 하는 소수는 7331이다. 7331은 소수인데, 신기하게도 733도 소수이고, 73도 소수 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 4 MB Gold 5 수학, 정수론, 백트래킹 문제 풀이 소수 구하는 문제를 마주쳤을 때 가장 먼저 떠오르는 풀이법은 에라토스테네스의 체이다. 하지만 소수인지 판별해야하는 수의 최대값은 99,999,999 이므로, 에라토스테네스의 체로 1부터 99,999,999 까지의 판별 정보를 저장하기 위해서는 4MB가 넘는 크기의 배열이 ..

문제 : https://www.acmicpc.net/problem/2166 2166번: 다각형의 면적 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 다각형을 이루는 순서대로 N개의 점의 x, y좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수이다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Gold 5 기하학 / 다각형의 넓이 문제 풀이 다각형의 각 꼭짓점 좌표가 순서대로 주어지기 때문에 첫 번째 점에서 각 점으로 선을 이어 만들어지는 삼각형들의 넓이를 모두 합해주면 된다. 흔히 신발끈 공식이라고 불리는 방법이다. 신발끈 공식을 이용하면 일반 다각형과 오목 다각형의 넓이 까지 수월하게 구할 수 있다. 그 원리는 아래 그림과 같다. 일반 다..

문제 : https://www.acmicpc.net/problem/17386 17386번: 선분 교차 1 첫째 줄에 L1의 양 끝 점 x1, y1, x2, y2가, 둘째 줄에 L2의 양 끝 점 x3, y3, x4, y4가 주어진다. 세 점이 일직선 위에 있는 경우는 없다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 0.25초 512 MB Gold 3 기하학 / 선분 교차 판정 문제 시간 제한이 0.25초이므로 사실 상 계산 공식을 통해 한 번에 답을 도출하라는 뜻이다. 처음에는 풀이법이 금방 생각나서 이게 왜 골드 3 짜리 문제인지 의문이었지만, CCW 알고리즘을 사용하지 않고는 기울기를 구하는 과정에서 소수점 오차까지 고려해야하기 때문인 것 같았다. CCW 알고리즘을 사용..

문제 : https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 128 MB Gold 5 수학 / 브루트포스 문제 풀이 최대공약수(G)와 최소공배수(L)이 주어졌을 때, 역으로 두 수 a, b를 구해야하는 문제다. 또한, a, b의 쌍이 여러개일 경우 a+b의 값이 최소가 되는 쌍을 찾아야 한다. 다 재쳐두고 먼저 G과 L에 대한 공식과 규칙들을 정리해봤다. - G * L = a * b - a = G ..

문제 : https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 1초 256 MB Gold 3 수학 / 누적합 문제 풀이 누적합 알고리즘을 응용해서 푸는 문제다. 하지만 시간 제한이 1초이므로 단순히 누적합 배열만 가지고 계산하려고 하면 시간 초과를 뱉어낸다. 또한 입력받는 수 A의 범위가 0

문제 : https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 64 MB Silver 1 수학 / 정수론 문제 풀이 c++로 풀이했을 때는 조금 복잡한 규칙을 만들어서 풀이했었는데, 정답이 잘 나와 다시 고민하지 않고 넘어갔었다. 하지만 파이썬으로 같은 풀이법을 옮겼더니 곧장 시간 초과를 뿜어내더라... 그래서 풀이 과정을 다시한번 되짚어보며, 계산이나 반복을 줄일 수 있는 방법을 찾아봤다. 문제의 정답..

문제 : https://www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 64 MB Gold 5 수학 / 구현 문제 풀이 수가 십의 제곱 단위로 커지는 구간 마다 수와 숫자의 개수는 다음과 같다. 한 자릿수 범위 (1~9) 수 : 9개 / 숫자 : 9개 두 자릿수 범위 (10~99) 수 : 90개 / 숫자 : 180개 세 자릿수 범위 (100~999) 수 : 900개 / 숫자 : 2700개 이 규칙을 다음과 같은 공식으로 정리할 수 있다. 수..

문제 주소 : https://www.acmicpc.net/problem/2022 2022번: 사다리 첫째 줄에 차례대로 x, y, c에 해당하는 양의 실수 세 개가 입력된다. 수는 소수점 여섯째 자리까지 주어질 수 있으며, 3,000,000,000보다 작거나 같다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 128 MB Gold 4 수학 / 기하학 / 이분 탐색 문제 풀이 ?를 w로 두고, 입력받는 변수 x, y, c를 활용해 다음과 같이 식을 정리할 수 있다. 위 과정을 통해 알아낸 최종식을 풀어 w를 알아내야 하지만, 루트와 제곱이 난무하는 복잡한 식이기 때문에 순수 계산으로는 답 계산이 어렵다. 따라서 w가 될 수 있는 최솟값과 최대값을 구하여 이분탐색을 통해 위..

문제 주소 : https://www.acmicpc.net/problem/1105 1105번: 팔 첫째 줄에 L과 R이 주어진다. L은 2,000,000,000보다 작거나 같은 자연수이고, R은 L보다 크거나 같고, 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 512 MB SILVER 1 수학 / 그리디 알고리즘 문제 풀이 L과 R 사이에 있는 수 중, 8이 가장 적게 들어있는 수에 8이라는 숫자가 몇 번 들어있는 지를 구하는 문제입니다. L과 R은 다음과 같은 두 가지 경우로 입력될 수 있습니다. 1. L과 R의 자릿수가 다르다. (ex. L:20, R:300) 2. L과 R의 자릿수가 같다. (ex. 20, 30) ..

문제 주소 : https://www.acmicpc.net/problem/15973 15973번: 두 박스 표준 입력으로 두 박스의 정보가 한 줄에 하나씩 주어진다. 각 박스의 정보는 왼쪽 아래 꼭짓점 좌표 (x1, y1)과 오른쪽 위 꼭짓점 좌표 (x2, y2)로 구성되는데 이들 좌푯값 x1, y1, x2, y2 (x1 < x2, y1 < y2) www.acmicpc.net 시간 제한 메모리 제한 난이도 알고리즘 분류 2초 512 MB SILVER 1 수학 / 기하학 / 많은 조건 분기 문제 풀이 코딩 알고리즘이 필요하다기보다는 수학적 아이디어가 필요한 문제였습니다. 하지만 그렇다고 복잡한 공식이 필요하진 않았고, 박스 Q가 P의 근처에서 움직일 수 있는 경로를 따져보며 정리해보니 생각보다 쉽게 풀렸습니..