www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net E, S, M 의 범위는 $ 1\leq E \leq15, 1\leq S \leq28, 1\leq M \leq19$으로 나올 수 있는 모든 경우의 수는 15 * 28 * 19 = 7980이다. 이 수는 큰 수가 아니므로 완전탐색의 방법을 이용하여 풀 수 있다. 1 에서 부터 1씩 증가시키면서 주어진 수와 같아질 때까지 비교했다. import sys input=sys.stdin.readline E, S, M = map(..

www.acmicpc.net/problem/3085 3085번: 사탕 게임 첫째 줄에 상근이가 먹을 수 있는 사탕의 최대 개수를 출력한다. www.acmicpc.net 처음에는 이 문제를 어떻게 풀어야할지 감이 안잡혔는데, 그냥 다 해보면 되는 거였다! 😀 그 이유는 테이블 크기가 50보다 작기 때문이다. 밑에 코드는 시간복잡도가 $O(N^4)$지만 애초에 테이블 크기가 작기 때문에 시간 초과가 나지 않는다. 인접한 두 칸을 고르고 사탕을 교환하는 방법은 상하좌우로 4가지가 있다. 그러나 테이블을 순차적으로 검사했을때, 위로 바꾸는 방법과, 왼쪽으로 바꾸는 방법은 이전에 검사했었으므로 다시 고려할 필요가 없다. 그러므로 밑으로 바꾸는 방법과, 오른쪽으로 바꾸는 방법 두 가지만 고려하면 된다. import..

www.acmicpc.net/problem/2309 2309번: 일곱 난쟁이 아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다. www.acmicpc.net 브루트포스 문제 유형중 그냥 다 해보기 유형에 해당한다. 🥲 여기서는 9명 중 7명을 고르는 것이나, 9명 중 2명을 고르는 것이나 똑같다. arr=[] for _ in range(9): arr.append(int(input())) arr.sort() sum_arr=sum(arr) for i in range(9): for j in range(i+1, 9): if sum_arr - (arr[i]+arr[j]) == 100..

www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 1부터 N까지 범위 안에 들어가는 모든 소수를 구하려면 에라토스테네스의 체를 사용한다. 에라토스테네스의 체 1. 2부터 N까지 모든 수를 써 놓는다. 2. 아직 지워지지 않은 수 중에서 가장 작은 수를 찾는다. 3. 그 수는 소수이다. 4. 이제 그 수의 배수를 모두 지운다. 이 문제를 해결하기 위해서는 배열이 필요하다. - 수를 지웠는지 아닌지 기록하는 배열 지움: True 지우지 않음: False import sys input=sys.st..

www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 소수: 약수가 1과 자기 자신밖에 없는 수 소수를 구하는 법에는 크게 두 가지가 있다. 1. 소수의 정의 이용 - N이 소수인지 알아보기 위하여 2 부터 N-1까지 나머지 연산을 해본다. - 시간복잡도 $O(n)$ 2. 약수의 특징 이용 - N의 가장 작은 약수는 2이다. 약수는 $\sqrt{N}$을 기준으로 대칭이다. 2의 대칭인 수는 $2/N$이다. $2/N+1$부터 N-1까지 약수가 없어야 소수 이므로 2부터 $N/2$까지 나누어 떨어지는지 검사한다. - 시간복잡도 $O(n..

www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 최대공약수(GCD): 두 수 A와 B의 최대공약수 G는 A와 B의 공통된 약수 중에서 가장 큰 정수이다. 최소공배수(LCM): 두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다. 최대공약수는 유클리드 호제법을 이용하여 구한다. - a를 b로 나눈 나머지를 r이라고 했을 때, GCD(a, b) = GCD(b, r) 이다. - r이 0이면 그 때 b가 최대 공약수이다. 최소공배수는 GCD를 응요해서 구할 수 있다. - 두 수 a, b의 최대공약수 g라고 했을 때..

17427 약수의 합2 문제와 매우 유사한 문제이다. 문제에서 요구하는 조건은 다음과 같다. - f(A) = A의 약수의 합 - g(N) = f(1) + f(2) + ... + f(N) - N이 주어졌을 때, g(N)을 구하는 문제 - 테스트 케이스의 갯수 약수의 합 2 문제에서 추가된 부분은 마지막 테스트 케이스의 개수이다. 우선 약수의 합 2 문제의 해결과 똑같이 풀면 다음과 같다. import sys input=sys.stdin.readline n = int(input()) for i in range(n): sum_ = 0 a = int(input()) for j in range(1, a+1): sum_ += (a//j)*j print(sum_) 그러나 이 코드는 바로 시간 초과가 뜬다. 그러므로,..

www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net - f(A) = A의 약수의 합 - g(N) = f(1) + f(2) + ... + f(N) - N이 주어졌을 때, g(N)을 구하는 문제 우선, 약수를 구하는 방법에는 두가지가 있다. 1. 자연수 N이 주어졌을 때, 1부터 N까지 나누어가면서 나머지가 0인 값을 구하는 방법 2. 자연수 N이 주어졌을 때, 약수는 서로 대칭구조를 이루고 있으므로 1부터..

www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되 www.acmicpc.net N의 진짜 약수 중 가장 작은 수와 큰 수를 곱하면 N이다. import sys input=sys.stdin.readline n=int(input()) # 리스트에 주어진 숫자를 입력 받는다. arr=list(map(int, input().split())) # 리스트에서 가장 큰 수를 구한다. max_=max(arr) # 리스트에서 가장 작은 수를 구한다. min_=min(arr) # 둘을 곱한 값을 출..

www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 최대 숫자가 20까지이므로 DP 테이블을 만들어 풀면 금방 끝낼 수 있다. 최대 숫자가 20이라 했으므로 행이 0부터 20까지 있고, 열이 n개 있는 DP 테이블을 생성한다. 계산해서 나온 값을 차례대로 DP 테이블에 기록한다. 이때 그냥 기록하는게 아닌 경우의 수를 기록해야한다. import sys input=sys.stdin.readline n=int(input()) dp=[[0 for _ in ra..