넘치게 채우기

https://leetcode.com/problems/count-the-number-of-computer-unlocking-permutations/description/?envType=daily-questionLeetCode - Count the Number of Computer Unlocking Permutations문제 유형: 수학, 조합론, 애드 혹문제 난이도: Medium 문제You are given an array complexity of length n.There are n locked computers in a room with labels from 0 to n - 1, each with its own unique password. The password of the computer i ha..

https://www.acmicpc.net/problem/4563BOJ - 피타고라스의 복수문제 유형: 정수론, 수학, 기하학문제 난이도: Gold V시간 제한: 1초메모리 제한: 128MB 문제피타고라스의 정리는 직각삼각형의 세 변의 관계를 나타내는 정리이다. 빗변의 길이를 C, 다른 두 변의 길이를 A, B라고 한다면 다음과 같은 식으로 쓸 수 있다.A^2 + B^2 = C^2세 변의 길이가 모두 자연수인 직각삼각형 중에 가장 유명한 삼각형은 아래와 같다.A = 12인 경우에는 다음과 같이 두 개의 직사각형을 찾을 수 있다.A가 주어졌을 때, 빗변의 길이 C가 자연수인 직각삼각형을 만드는 자연수 B (B > A)는 몇 개가 있을까? 입력입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이..

https://www.acmicpc.net/problem/15979BOJ - 스승님문제 유형: 수학, 애드혹, 정수론, 유클리드 호제법문제 난이도: Silver II시간 제한: 1초메모리 제한: 512MB 문제현욱은 옛날 자신에게 알고리즘을 가르쳐 준 스승님이 어느 신비로운 밀림 속 나무 아래에서 수행 중이라는 사실을 전해 들었다.이 무한한 넓이의 밀림에는 모든 격자점(x, y 좌표가 모두 정수인 위치)마다 완전히 똑같은 모양의 나무가 한 그루씩 심어져 있고, 현욱의 스승은 그 중 (M,N) 좌표의 나무 아래에서 수행을 하고 있다.이 밀림에는 또 다른 특징이 있는데, 어떤 나무 아래에서 볼 수 있는 다른 나무로 순간이동을 할 수 있다는 것이다. 어떤 나무 아래에서 다른 나무를 보려면, 그 두 나무의 좌표..

https://www.acmicpc.net/problem/12911BOJ - 좋아하는 배열문제 유형: 수학, 정수론, 다이나믹 프로그래밍문제 난이도: Gold II시간 제한: 2초메모리 제한: 512MB 문제성관이는 다음과 같은 성질을 만족하는 배열을 좋아한다.배열의 길이는 N이다.배열에 채워져있는 수는 1보다 크거나 같고, K보다 작거나 같은 자연수이다.배열에서 연속한 수가 A와 B일 때, A 예를 들어, N = 4, K = 7인 경우에 [1, 7, 7, 2]는 성관이가 좋아하는 배열이다. 모든 연속한 수가 1 N과 K가 주어졌을 때, 성관이가 좋아하는 배열의 경우의 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000) 출력첫째 줄..

https://www.acmicpc.net/problem/11525BOJ - Farey Sequence문제 유형: 수학, 정수론, 오일러 피 함수, 누적 합문제 난이도: Gold I시간 제한: 1초메모리 제한: 256MB 문제Given a positive integer, N, the sequence of all fractions a / b with (0 For example, the Farey Sequence of order 6 is:0/1, 1/6, 1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5, 5/6, 1/1For this problem, you will write a program to compute the length of the Farey sequence of ..

https://www.acmicpc.net/problem/9326BOJ - MI6문제 유형: 수학, 정수론, 소수판정문제 난이도: Gold III시간 제한: 1초메모리 제한: 128MB 문제MI6는 스파이의 신원을 확인하기 위해서 스파이 식별 코드(Spy Identification Code, SIC)를 사용한다. 예를 들어, 제임스 본드의 SIC는 7이다.MI6는 스파이의 그룹과 그룹에 속하는 스파이를 쉽게 알아볼 수 있게 하기 위해 SIC를 할당한다. 그룹은 상태 코드로 나타낼 수 있는데, 상태 코드는 그룹에 속하는 모든 스파이의 SIC를 곱한 값이다.상태코드의 효율성을 위해, 2보다 크거나 같은 모든 상태코드에 대해서, 각 상태코드를 가지는 스파이 그룹이 유일하게 존재하고, 각 스파이 그룹사이의 상태코..

https://www.acmicpc.net/problem/1188BOJ - 음식 평론가문제 유형: 수학, 정수론, 유클리드 호제법문제 난이도: Gold IV시간 제한: 1초메모리 제한: 128MB 문제선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있..

https://www.acmicpc.net/problem/1153BOJ - 네 개의 소수문제 유형: 수학, 정수론, 소수 판별, 에라토스테네스의 체문제 난이도: Gold III시간 제한: 2초메모리 제한: 128MB 문제임의의 자연수가 주어지면, 이를 네 개의 소수의 합으로 분해하는 프로그램을 작성하시오. 예를 들어 38 = 5 + 7 + 13 + 13이 된다. 입력첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 출력첫째 줄에 네 개의 소수를 빈 칸을 사이에 두고 순서대로 출력한다. 불가능한 경우는 -1을 출력한다. 풀이우선, 에라토스테네스의 체를 이용해서 소수들을 걸러준다. 골드바흐 추측으로 풀 수 있다고 한다. 골드바흐 추측은 2보다 큰 모든 짝수는 두 소수의 합으로 표현될 수 있..

https://www.acmicpc.net/problem/25823BOJ - 조합의 합의 합문제 유형: 조합, 수학, 정수론문제 난이도: Gold I시간 제한: 1초메모리 제한: 512MB 문제양의 정수 M이 주어질 때 다음 식의 값을 구하는 프로그램을 작성하시오. ∑n=3M∑k=0n(nk)2이때 (nk)는 이항계수를 의미한다.단, 답이 너무 커질 수 있으니 10^9+7로 나눈 나머지를 출력한다. 입력첫째 줄에 정수 M이 주어진다. (3≤M≤200000) 출력첫째 줄에 문제에서 주어진 식의 값을 10^9+7로 나눈 나머지를 출력한다. 풀이 이다.독립되게 n개에서 k개뽑기의 합은 2n개에서 n개뽑기와 같다.첫 조합에서 k개를 뽑고, 그 다음 두 번째 조합에서 n-k개를 선택한다고 보면 된다. 이제, 페르마..

https://www.acmicpc.net/problem/14949BOJ - 외계 미생물문제 유형: 수학, 조합론, 정수론, 다이나믹 프로그래밍문제 난이도: Gold I시간 제한: 2초메모리 제한: 256MB 문제항상 B, C가 가득 찬 성적표를 보고 자신이 컴퓨터 공학에 크게 재능이 없다고 생각한 윤영이는 결국 전공을 바꾸어 항공우주학과와 생물학과를 복수전공 하였고, 외계 생물 연구가로 큰 성공을 거두었다.그러던 중 어떤 행성에서 특이한 외계 미생물을 발견하게 되었고, 이를 신기하게 생각했던 윤영이는 몇 마리를 자신의 연구소로 가지고 왔다. 연구 결과 미생물은 다음과 같은 특징을 가지고 있음을 확인할 수 있었다.미생물은 스스로 자식을 낳으며, 하루동안 모든 자식을 낳고 죽는다. 낳을 수 있는 자식의 수..