https://www.acmicpc.net/problem/1017 1017번: 소수 쌍 지민이는 수의 리스트가 있을 때, 이를 짝지어 각 쌍의 합이 소수가 되게 하려고 한다. 예를 들어, {1, 4, 7, 10, 11, 12}가 있다고 하자. 지민이는 다음과 같이 짝지을 수 있다. 1 + 4 = 5, 7 + 10 = 17, 11 + www.acmicpc.net 난이도 : 플래티넘 3 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체, 이분 매칭 설명 소수 판정 + 이분 매칭 문제입니다. 이분 매칭에 관해서는 아래 글을 참고해주세요. https://uknowblog.tistory.com/444 [알고리즘] 이분 매칭 (Bipartite Matching) 이분 매칭을 간단히 이야기하면 연애 매칭 프로..

https://www.acmicpc.net/problem/1963 1963번: 소수 경로 소수를 유난히도 좋아하는 창영이는 게임 아이디 비밀번호를 4자리 ‘소수’로 정해놓았다. 어느 날 창영이는 친한 친구와 대화를 나누었는데: “이제 슬슬 비번 바꿀 때도 됐잖아” “응 지금 www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프 이론, 그래프 탐색, 정수론, 너비 우선 탐색, 소수 판정, 에라토스테네스의 체 설명 한 번에 한 글자씩 수를 바꿀 수 있으며, 바꾼 숫자는 소수여야 합니다. 목표 숫자로 바꾸는 최소 횟수를 출력하는 문제입니다. 너비 우선 탐색(BFS)을 사용해 '숨바꼭질' 문제와 같이 최단 경로(최소 횟수)를 찾는 문제입니다. https://www.acmicpc.net/prob..

https://www.acmicpc.net/problem/17471 17471번: 게리맨더링 선거구를 [1, 4], [2, 3, 5, 6]으로 나누면 각 선거구의 인구는 9, 8이 된다. 인구 차이는 1이고, 이 값보다 더 작은 값으로 선거구를 나눌 수는 없다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 그래프이론, 브루트포스 알고리즘, 그래프 탐색, 너비 우선 탐색, 조합론, 깊이 우선 탐색 설명 위와 같이, 하나의 시를 2개의 선거구로 나누려 합니다. 선거구의 각 구역은 모두 직/간접적으로 이어져 있어야 하며,이때 두 선거구 간의 인원 수의 차이가 최소가 되어야 합니다. n이 2 !selected[index] }.sum() // 선거구2 인구 수 answer = minOf(ans..

https://www.acmicpc.net/problem/20302 20302번: 민트 초코 상원이가 고른 디저트가 “민트 초코”인 경우 mint chocolate, “치약”인 경우 toothpaste를 출력한다. www.acmicpc.net 난이도 : 골드 4 태그 : 수학, 정수론, 소수판정, 에라토스테네스의채 설명 상당히 어려웠던 문제였습니다 그냥 단순히 입력으로 주어지는 연산을 그대로 했더니 당연하게 시간초과 발생하였고, *, / 연산을 각각 리스트로 만들어 6 -> 2 * 3, 10 -> 2 * 5와 같이 소인수 분해 한 후, 각각에 리스트에 넣어준 뒤 (첫 항은 *로 처리), * 연산이 남아있으면 유리수, / 연산이 남아있으면 유리수로 판단하였습니다. 6 / 4 = (3 * 2) / (2 * ..

https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 난이도 : 실버 3 태그 : 수학, 기하학, 많은 조건 분기 설명 x1, y1과 반지롬 x2, y2와 반지름이 주어졌을 때, 위치의 개수를 출력하는 문제입니다. 즉, 외접하거나 내접하는 경우를 찾으면 되겠네요. 위치의 개수가 무한대일 경우 두 원이 일치할 경우, 적이 있을 수 위치는 무한대입니다. 위치의 개수가 0개일 경우 터렛의 두 사람의 위치가 같으나, 반지름이 다를 때, 두 원은 서로 교차하지 않습니다. 따라서 적이 있을 수 있는 위치의 경우..

https://www.acmicpc.net/problem/6588 6588번: 골드바흐의 추측 각 테스트 케이스에 대해서, n = a + b 형태로 출력한다. 이때, a와 b는 홀수 소수이다. 숫자와 연산자는 공백 하나로 구분되어져 있다. 만약, n을 만들 수 있는 방법이 여러 가지라면, b-a가 가장 큰 www.acmicpc.net 난이도 : 실버 1 태그 : 수학, 정수론, 소수 판정, 에라토스테네스의 체 설명 골드바흐 추측은 4보다 큰 모든 짝수는 두 홀수 소수의 합으로 나타낼 수 있다. 라는 추측입니다. 아직 수학적으로 증명되지 않았기에 추측이라고 불립니다. 4보다 큰 짝수를 두 홀수 소수의 합으로 나타낼 수 있을 경우, 두 소수의 차이가 가장 큰 두 수를 출력, 나타낼 수 없을 경우 "Goldb..

https://www.acmicpc.net/problem/5988 5988번: 홀수일까 짝수일까 짝이 없는 경재는 매일 홀로 있다보니 홀수를 판별할 수 있는 능력이 생겼다. 창식이는 경재의 말이 사실인지 그 능력을 시험해보려 한다. 창식이의 의심이 끝이 없을 것 같아 N개만 확인하기 www.acmicpc.net 난이도 : 브론즈 3 태그 : 수학, 문자열, 사칙연산, 임의 정밀도 / 큰 수 연산 설명 수를 입력받고 이 수가 짝수라면 even을, 홀수라면 odd를 출력하는 문제입니다. 단순히 수를 입력받고 이를 2로 나눴을 때 나머지를 구할 경우, K (1

https://www.acmicpc.net/problem/27331 27331번: 2 桁の整数 (Two-digit Integer) 2 つの数字 A, B が与えられる． 十の位が A であり，一の位が B である 2 桁の正の整数を出力せよ． www.acmicpc.net 난이도 : 브론즈 5 태그 : 수학, 구현, 사칙연산 설명 일본 여행을 왔습니다. 그동안 열심히 달려온 만큼 잠시 재충전 시간을 가지고 있으나, 그렇다고 해서 1일 1코테를 쉴 수는 없으므로 좀 쉬운 문제 중에서도 일본어 문제 하나를 선택했습니다. 해당 문제는 숫자 두 개가 주어졌을 때, 첫 번째는 십의 자리, 두 번째는 일의 자리 숫자이며, 이 두 숫자를 합한 숫자를 출력하는 것이 목표입니다. 첫 번째 숫자에 10을 곱하고 두 번째 숫자를 더하여..

https://www.acmicpc.net/problem/4344 4344번: 평균은 넘겠지 대학생 새내기들의 90%는 자신이 반에서 평균은 넘는다고 생각한다. 당신은 그들에게 슬픈 진실을 알려줘야 한다. www.acmicpc.net 난이도 : 브론즈 1 태그 : 수학, 사칙연산 설명 예전에 푼 문제였던 것 같은데, 오늘 확인해보니 갑자기 틀렸습니다로 뜨길래 뭔가 했더니, 테스트 케이스가 추가되어 재채점 되었더군요. 코틀린 혹은 파이썬으로 해당 문제를 풀 경우 애로사항 중 하나가 바로 반올림하는 부분일 것 같습니다. 이전에 포스팅했던 내용인 오사오입 방식 때문인데요. https://uknowblog.tistory.com/338 코틀린의 반올림 방식 : 오사오입 kotlin.math.round()... 뭔..

https://www.acmicpc.net/problem/18110 18110번: solved.ac 5명의 15%는 0.75명으로, 이를 반올림하면 1명이다. 따라서 solved.ac는 가장 높은 난이도 의견과 가장 낮은 난이도 의견을 하나씩 제외하고, {5, 5, 7}에 대한 평균으로 문제 난이도를 결정한다. www.acmicpc.net 난이도 : 실버 4 태그 : 수학, 구현, 정렬 설명 Solved.ac 의 문제 난이도 계산 방법을 바탕으로 만든 문제인 것 같네요. 솔브드의 난이도 계산 시스템은 극단적인 값으로 인해 평균이 왜곡되는 것을 막기 위해 절사 평균을 사용하는데요. 단순히 의견 개수 * 0.15 (반올림)개 만큼 양극값을 제거하고 평균을 계산하면 됩니다. 소스코드 fun main() = w..