문제 https://www.acmicpc.net/problem/14728 Algorithm 전형적인 배낭 문제이다. dp[i][j] : i번째 단원까지 고려했을 때, 총 공부 시간이 j일때 얻을 수 있는 최대 점수 점화식 : dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i].first] + v[i].second - dp[i - 1][j]는 i번째 단원을 선택하지 않는 경우, i번째 단원을 고려하지 않고 이전 단원까지의 최대 점수 - dp[i - 1][j - v[i].first] + v[i].second는 i번째 단원을 공부하기 위해 필요한 시간 v[i].first가 j보다 작거나 같은 경우에만 가능하다. 선택하는 경우에는 해당 단원을 선택하기 전까지의 최대 점수에 현재..
전체 글
항공대 알고리즘 동아리 Koala 🥰
https://www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 문제 분석 문제 설명 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. 입력 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000) 출력 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다. 소스코드 import java.io.BufferedReader; im..
나중 결과의 출력값으로 대학 이름이 나와야 하므로 처음에 Soongsil, Korea, Hanyang 변수에 입력하도록 하였다. sort 메서드를 사용하기 위해 위의 변수들을 리스트 요소로 대입하였고 univ 리스트의 원래 순서가 필요하진 않은 상황이라 따로 다른 리스트를 등장시키지 않고 sort 메서드를 사용하였다. 문제 조건에서 세 대학의 총점이 100점 이상이면 OK를 출력해야 한다고 했으므로 if 조건에 sum 함수를 이용하여 univ 리스트 요소들의 총합을 구하여 조건문을 작성하였다. 100점 미만일 경우, 최저점을 가진 대학을 찾는 이중 조건문을 밑에 붙였다. sort 메서드를 사용하였으므로 univ[0]이 최저점이고 위에 변수도 같이 할당하여 각각의 대학 이름과 비교하는 코드를 작성하였다.
https://www.acmicpc.net/problem/1932 1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net dp(동적 계획법 - Dynamic Programming)인 문제이다. 처음에 봤을 때는 그리디가 생각이 났지만, 현재 기준으로 높은 숫자가 아닌, 합 중 최대값을 출력해야되므로 dp를 이용하여 풀어야 된다. 양 끝에 있는 숫자들은 더할 수 있는 값들이 정해져있으므로, 제일 왼쪽과 제일 오른쪽의 숫자들은 이전 값들과 누적된 합들을 합해준다. 그리고 중간에 있는 값들은 dp 내에 있는 현재 idx와 이전 idx 값 중 비교하여 큰 값을 불러와서 출력하도록 한다. 그 부분..
문제 https://www.acmicpc.net/problem/14430 14430번: 자원 캐기 인류의 차세대 인공지능 자원 캐기 로봇인 WOOK은 인간 대신 자원을 캐는 로봇이다. WOOK은 언제나 제한된 범위 내에서 자원을 탐색하며, 왼쪽 위 (1, 1)부터 오른쪽 아래 (N, M)까지 자원을 탐색한다. www.acmicpc.net Algorithm 인공지능 WOOK은 오른쪽(r, c+1)과 왼쪽(r+1, c) 방향으로만 움직일 수 있다. 따라서, 현재 위치와 이전에 기록해둔 최댓값을 이용한다. 즉, DP의 Memoization을 활용하여 풀이한다.주의할 점은 인덱싱이다. 가장 윗줄과 왼쪽줄은 먼저 채워주고, 1부터 n까지 기록하도록 한다. Code n,m=map(int,input().split()..
문제 요약 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%동전을 해준다 코드