![]()
문제 요약 3kg과 5kg 설탕으로 최소 봉지를 사용하여 nkg을 만드는 방법 입력 만들어야할 설탕 kg N (3 ≤ N ≤ 5000) 출력 봉지의 최소 개수, 만들 수 없다면 -1 코드 입력을 받고 입력의 범위에 따라 dp의 크기를 선언한다. dp=[-1]*n으로 할 시에는 n=1일 경우 5,6,7에 미리 정의해둔 값들이 인덱스 밖의 값이 되므로 주의해야한다. 이 문제는 다이나믹 프로그래밍으로 푸는 문제이다. 큰 문제를 작은 문제로 쪼개는 다이나믹 프로그래밍의 형태처럼 dp[i-3], dp[i-5]의 값을 참고하여 dp[i]의 값을 정의한다. dp[i]의 값이 궁금할때 dp[0]~dp[i-1]까지의 값은 모두 최소값으로 이미 정의되어있으므로 이를 쉽게 참고할 수 있다! 따라서 첫번째 if 문에서는 dp..
![]()
https://www.acmicpc.net/problem/17219 17219번: 비밀번호 찾기 첫째 줄에 저장된 사이트 주소의 수 N(1 ≤ N ≤ 100,000)과 비밀번호를 찾으려는 사이트 주소의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 두번째 줄부터 N개의 줄에 걸쳐 각 줄에 사이트 주소와 비밀번 www.acmicpc.net 문제 분석 문제 설명 2019 HEPC - MAVEN League의 "비밀번호 만들기"와 같은 방식으로 비밀번호를 만든 경민이는 한 가지 문제점을 발견하였다. 비밀번호가 랜덤으로 만들어져서 기억을 못 한다는 것이었다! 그래서 경민이는 메모장에 사이트의 주소와 비밀번호를 저장해두기로 했다. 하지만 컴맹인 경민이는 메모장에서 찾기 기능을 활용하지 못하고 직접 눈으로 사이..
https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제 국가의 수 N(1 n >> k; for (int i = 0; i > a >> b >> c >> d; v.push_back({ {b,c},{d,a} }); } sort(v.rbegin(), v.rend()); for (int i = 0; i < v.size(); i++) { if (v[i].second.second == k) break; if..
![]()
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 코드 from functools import reduce def in_cache(func): # decorator를 사용 - 메모이제이션 cache = {} def wrapper(n): if n in cache: return cache[n] else: cache[n] = func(n) return cache[n] return wrapper @in_cache def factorial_reduce(n): # redu..
https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, www.acmicpc.net 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 ..
https://www.acmicpc.net/problem/12780 12780번: 원피스 바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항 www.acmicpc.net 문제 바야흐로 지금은 대해적 시대, 밀짚모자 해적단의 선장 교정이는 어린 시절 우연히 잊지 못할 한 마디를 들었다. 그것은 바로 해적 왕 골.D.상윤이 자신이 모은 모든 보물인 원피스를 위대한 항로에 놓고 왔다는 것이었다. 원피스를 가진 자는 이 세상을 가질 수 있다는 매혹적인 얘기였다. 모두들 말도 안 된다고 고개를 저었지만 교정이는 동료를 모아 원피스를 찾아 여행을 떠났다. 하늘섬을 지나 어인섬도..
![]()
https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 풀이 동전의 사용하는 개수의 최소를 구해야 하기 때문에 처음에는 list를 만들고 동전의 종류를 넣은후 큰것 부터 작은것 순으로 비교하여 동전이 금액의 크기보다 작으면 동전 사용 개수의 변수 c와 금액의 변수 m에 각각 c+=금액//동전 을 해주고 m=m%동전을 해준다 코드
![]()
문제 링크 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 풀이 상근이가 왼쪽부터 숫자들을 더하거나 빼나가며 최우항의 숫자를 만드는 경우의 수를 출력하는 문제이다. 완전 탐색을 사용하면 단순하게 생각하였을 때 O(2^n)의 시간복잡도를 가지기 때문에 패턴을 찾아 문제를 풀어야 한다. 문제 설명 중 "상근이는 아직 학교에서 음수를 배우지 않았고, 20을 넘는 수는 모른다. 따라서, 왼쪽부터 계산할 때, 중간에 나오는 수가 모두 0 이..
문제 https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net 코드 #include #include #include using namespace std; /* 계단 오르기(2579) 계단 아래 시작점부터 계단 꼭대기에 위치한 도착지까지 가야함 각각의 계단에는 일정한 점수가 쓰여 있음. 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 됨 계단을 오르는 규칙 1. 계단은 한번에 1 혹은 2 계단 씩 오를 수 있음 2. 연속된 세개의 계단을 모두 밟아소는 안됨 3. 마지..
![]()
https://www.acmicpc.net/problem/2711 2711번: 오타맨 고창영 첫째 줄에 테스트 케이스의 개수 T(1
문제 영어 문장속 숨어있는 니모(Nemo)를 찾아보자. 니모를 찾는데 있어서 대소문자는 중요하지 않다. 여러 문장이 각 줄로 입력되며, 입력의 마지막에는 "EOI" 입력된다. 한 줄은 최대 80개의 글자로 이루어져 있다. 숨겨진 니모를 찾으면 “Found”, 못찾으면 “Missing”를 각 줄에 맞게 출력하면 된다. 코드 def find_nemo(sentence): # 대소문자를 구분하지 않고 소문자로 변환하여 니모를 찾음 if 'nemo' in sentence.lower(): return "Found" else: return "Missing" # 입력을 받아 니모를 찾고 결과를 출력 while True: try: line = input().strip() if line == "EOI": break pri..
https://www.acmicpc.net/problem/10824 10824번: 네 수 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) www.acmicpc.net 문제 네 자연수 A, B, C, D가 주어진다. 이때, A와 B를 붙인 수와 C와 D를 붙인 수의 합을 구하는 프로그램을 작성하시오. 두 수 A와 B를 합치는 것은 A의 뒤에 B를 붙이는 것을 의미한다. 즉, 20과 30을 붙이면 2030이 된다. 입력 첫째 줄에 네 자연수 A, B, C, D가 주어진다. (1 ≤ A, B, C, D ≤ 1,000,000) 출력 A와 B를 붙인 수와 C와 D를 붙인 수의 합을 출력한다. 소스코드 #include #include using namespa..
