목록정수론 (22)
넘치게 채우기
https://www.acmicpc.net/problem/14949BOJ - 외계 미생물문제 유형: 수학, 조합론, 정수론, 다이나믹 프로그래밍문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제항상 B, C가 가득 찬 성적표를 보고 자신이 컴퓨터 공학에 크게 재능이 없다고 생각한 윤영이는 결국 전공을 바꾸어 항공우주학과와 생물학과를 복수전공 하였고, 외계 생물 연구가로 큰 성공을 거두었다.그러던 중 어떤 행성에서 특이한 외계 미생물을 발견하게 되었고, 이를 신기하게 생각했던 윤영이는 몇 마리를 자신의 연구소로 가지고 왔다. 연구 결과 미생물은 다음과 같은 특징을 가지고 있음을 확인할 수 있었다.미생물은 스스로 자식을 낳으며, 하루동안 모든 자식을 낳고 죽는다. 낳을 수 있는 자식의 수..
https://leetcode.com/problems/apply-operations-to-maximize-score/description/leetcode - Apply Operations to Maximize Score문제 유형: 모노토닉 스택, 스택, 그리디, 정수론, 정렬문제 난이도: Hard 문제You are given an array nums of n positive integers and an integer k.Initially, you start with a score of 1. You have to maximize your score by applying the following operation at most k times:Choose any non-empty subarray nums[l,..
https://www.acmicpc.net/problem/1241BOJ - 머리 톡톡문제 유형: 수학, 정수론문제 난이도: Gold V시간 제한: 2초메모리 제한: 128MB 문제엄지 생일 기념으로 학생들은 파티를 하고 있다. 엄지는 N(1≤N≤100,000)명의 학생에게 1부터 N번까지 차례대로 번호를 부여하였고 그들을 순서대로 빙 둘러앉아 원을 만들게 하였다. (즉 i번째 학생은 i-1과 i+1학생 사이에 앉아있다. 단, N번째 학생은 N-1번째 학생과 첫 번째 학생 사이에 앉아있다.)N명의 학생은 둘러앉아 "머리톡톡" 게임을 하려한다. 게임 규칙은 다음과 같다. 각각의 학생은 자신의 머리 위에 1,000,000 이하의 자연수 중 하나를 쓴다. 그리고 1번부터 N번 학생까지 한 명씩 차례대로 일어나 ..
https://www.acmicpc.net/problem/2737 BOJ - 연속 합문제 유형: 수학, 정수론문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제대부분의 양의 정수는 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있다.예를 들면 다음과 같다.6 = 1 + 2 + 39 = 5 + 4 = 4 + 3 + 2하지만, 8은 연속된 자연수 합으로 나타낼 수가 없다.자연수 N이 주어졌을 때, 이 수를 적어도 2개 이상의 연속된 자연수의 합으로 나타낼 수 있는 경우의 수를 출력하시오. 입력첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 정수 하나로 이루어져 있다. 이 정수는 문제에서 설명한 N이며, 231보다 작다. 출력각 테스트 케이스에 대해서 N을 적..
https://www.acmicpc.net/problem/27172BOJ - 수 나누기 게임문제 유형: 수학, 정수론문제 난이도: Gold IV시간 제한: 1초메모리 제한: 1024MB 문제《보드게임컵》을 준비하다 지친 은하는 보드게임컵 참가자들을 경기장에 몰아넣고 결투를 시키는 게임 《수 나누기 게임》을 만들었습니다.《수 나누기 게임》의 규칙은 다음과 같습니다.게임을 시작하기 전 각 플레이어는 1
https://www.acmicpc.net/problem/1644BOJ - 소수의 연속합문제 유형: 수학, 정수론, 슬라이딩 윈도우문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.3 : 3 (한 가지)41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)53 : 5+7+11+13+17 = 53 (두 가지)하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+..
https://codeforces.com/contest/2043/problem/BEducational Codeforces Round 173(Div.2) - B. Digits문제 유형: 수학, 정수론시간 제한: 1초메모리 제한: 256MB 문제Artem wrote the digit d">d on the board exactly n!">n! times in a row. So, he got the number dddddd…ddd">dddddd…ddd (exactly n!">n!digits).Now he is curious about which odd digits from 1">1to 9">9 divide the number written on the board. Artem은 정수 d를 정확히 n!..
https://www.acmicpc.net/problem/31288BOJ - 캬루문제 유형: 수학, 애드 혹, 해 구성하기, 정수론문제 난이도: Silver II시간 제한: 1초메모리 제한: 1024MB 문제이번에 캬루는 소수를 배신했다. 소수의 한 자리를 바꾸어서 소수가 아니게 만들어버렸다. 구체적으로는, 0으로 시작하지 않는 N자리 소수 P에 대해 어떤 수 Q가 P-캬루라는 것은 다음을 모두 만족하는 것을 의미한다. Q는 2 이상의 N자리 정수이며, 0으로 시작하지 않는다. P와 Q의 서로 다른 자릿수는 하나뿐이다. Q는 소수가 아니다.다음은 N=2,P=19일 때 P-캬루와 P-캬루가 아닌 수의 예시이다. Q=9는 1자리 정수이므로 19-캬루가 아니다. 09처럼 수가 0으로 시작할 수는 없다. Q=9..
https://www.acmicpc.net/problem/1124BOJ - 언더프라임문제 유형: 수학문제 난이도: Silver I시간 제한: 2초메모리 제한: 128MB 문제자연수 X를 소인수분해하면, 곱해서 X가 되는 소수의 목록을 얻을 수 있다. 예를 들어, 12 = 2 × 2 × 3이다. 1은 소수가 아니다.어떤 수 X를 소인수분해 해서 구한 소수의 목록의 길이가 소수이면, 그 수를 언더프라임 이라고 한다. 12는 목록에 포함된 소수의 개수가 3개이고, 3은 소수이니 12는 언더프라임이다.두 정수 A와 B가 주어졌을 때, A보다 크거나 같고, B보다 작거나 같은 정수 중에서 언더프라임인 것의 개수를 구해보자. 입력첫째 줄에 두 정수 A와 B가 주어진다. 2 출력첫째 줄에 A보다 크거나 같고, B보..
https://www.acmicpc.net/problem/13172BOJ - Σ문제 유형: 정수론, 분할 정복문제 난이도: Gold IV시간 제한: 1초메모리 제한: 512MB 문제실제로 존재하는지 아닌지는 차치하고, 당신에게 삼면체 주사위가 있어서 이 주사위를 굴린다고 생각해보자. 주사위를 굴렸을 때 각 면이 나올 확률은 모두 동일하게 1/3 이다. 한 면에는 1, 다른 한 면에는 2, 남은 한 면에는 4가 적혀있다고 하면 주사위를 굴렸을 때 나오게 되는 숫자의 기댓값은 과연 몇일까? 간단하게도 셋의 평균인 7/3이 될 것이다.이 문제를 조금 확장해서, "N면체 주사위의 각 면에 적힌 수가 주어졌을 때, 주사위를 굴렸을 때 각 면이 나올 확률이 모두 같다면 주사위를 굴렸을 때 나오게 되는 수의 기댓값은..