본문 바로가기

전체 글161

*[Python] 12865-평범한 배낭 1. 개념 정의 - N: 물품의 수(1 ≤ N ≤ 100) - K: 버틸 수 있는 무게(1 ≤ K ≤ 100,000) - W: 물건의 무게(1 ≤ W ≤ 100,000) - V: 물건의 가치(0 ≤ V ≤ 1,000) 2. 문제 이해 - 준서는 여행을 떠나며 N개의 물건을 챙긴다. 각 물건은 (무게 W, 가치 V)를 가진다. 배낭에 넣은 물건의 V 만큼 준서는 즐길 수 있다. 다만 최대 K무게까지만 들고 다닐 수 있다. 이제 준서가 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 구해야 한다. 3. 로직 짜기 1. 가치 V를 내림차순으로 정렬 후 K를 넘지 않게 해서 가방에 넣으면? - 최대 가치의 무게가 지나치케 클 경우 최적화 불가능 2. 무게당 가치(가치/무게)가 큰 순으로 내림차순 정렬 후 차례대로.. 2020. 10. 27.
[Python] 1026-보물 > 출처 : www.acmicpc.net/problem/1026 N = int(input()) A = list(map(int, input().split())) B = list(map(int, input().split())) A.sort() B.sort(reverse=True) S = sum(map(lambda x: x[0]*x[1], zip(A,B))) print(S) 2020. 10. 27.
*[Python] 1904-01타일 > 출처: www.acmicpc.net/problem/1904 - 아쉬운 점: - 동적 프로그래밍의 개념을 알고 있었지만 풀지 못했다 - 문제의 핵심을 찌르는 점화식을 발견해야겠다 N = int(input()) dp = [0] * 1000001 dp[1] = 1 dp[2] = 2 for i in range(3, N+1): dp[i] = (dp[i-2] + dp[i-1]) % 15746 print(dp[N]) 2020. 10. 26.
[Python] 13300-방 배정 > 출처: www.acmicpc.net/problem/13300 * 핵심 로직: - 학년별, 성별 반이 달라야한다 -> 리스트로 구분 - 같은 학년, 같은 성별의 학생수가 K보다 클 경우 - 방을 1개 늘리고 (학생수 - K) 를 반복한다 ** 아쉬운 점: - 이 문제는 사실 while문을 굳이 돌리지 않고도, - if (학생 수 % K == 0) 이면, cnt += 학생 수 // K - else 이면, cnt += 학생 수 // K + 1 로 간단하게 해결할 수 있었다 N, K = map(int, input().split()) student = [[0, 0] for _ in range(6)] for _ in range(N): S, Y = map(int, input().split()) student[Y-.. 2020. 10. 26.

티스토리툴바