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..

www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net knapsack 이라는 알고리즘으로 풀었다. DP 테이블을 2차원으로 만들어 값을 채워주면 된다. 값을 채워주는 수식은 다음과 같다. 최대 무게를 초과할 때는 이전가치를 넣고, 최대 무게를 초과하지 않는다면 이전가치와 새로운 가치와 이전 것의 물품을 뺀 가치를 더한 것 중에서 더 큰 값을 넣어주면 된다. 그렇게해서 나온 DP 테이블은 다음과 같다..

www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net import sys input=sys.stdin.readline n=int(input()) T=[] P=[] for _ in range(n): a, b=map(int, input().split()) T.append(a) P.append(b) # DP 테이블 초기화 dp=[0]*(n+1) for i in range(n): # 앞으로 남은 날(n-i) 안에 끝날 수 있다면 if T[i]