본문 바로가기

전체 글

 (107)
[백준] 1026 보물 Greedy python lv4 배열 a,b가 존재하고b의 순서는 바꾸지 않으면서, a의 순서만 바꿔서i번째 a,b 원소의 곱의 총 합이 최소가 되도록 만드는 것https://www.acmicpc.net/problem/1026 혹시 a와 b에 sort를 써도 정답 처리가 되나 궁금했는데그냥a.sort(reverse=Ture) b.sort()를 한 후 곱을 구해도 정답처리가 되긴 하더라 n = int(input())a = list(map(int,input().split()))b = list(map(int,input().split()))a.sort(reverse=True)b.sort()s=0for i in range(n): s+=a[i]*b[i]print(s)  근데 다른 사람들도 sort 써도 되는지 다 한번씩 해본게 좀 웃겼음 그..
[백준] 2217 로프 Greedy python 실4 로프가 k개면 각 로프에 w/k만큼 중량이 걸림 결국 물건 드는 데 쓰는 로프 중 가장 힘이 약한 로프*k개 만큼만 들 수 있음 그래서 로프를 힘 크기 오름차순으로 sort한 후에 첫번째 로프(가장 힘이 약한 로프)부터 보면첫번째 로프*n이 들 수 있는 최대무게 두 번째 로프*(n-1)이 최대 무게세 번째 로프*(n-2)가 최대 무게 따라서 i번째에는(i는 0부터 n-1까지)i번째 힘을 가진 로프*(n-i개)의 값을 구하면 n-i개의 로프를 사용했을 때 들 수 있는 최대 무게를 구할 수 있음 결국 이 값들을 다 dp에 저장한 후에max값을 구하면 됨 n = int(input())arr = [int(input()) for _ in range(n)]# 로프 k개이면, 각 로프에는 w/k 만큼 중량이 걸림ar..
[백준] 최대 공통 증가 수열(실패...) 7476 골1 오블챌을 위해 일단 풀 문제 선언만 하고 글 쓸게요...다시 돌아와서 풀고 수정하겠습니다 요즘 본인의 부분수열 실력 부족에 심각성을 느끼고... 부분 수열 좀 백준에서 찾아 풀겠습니다 https://www.acmicpc.net/problem/7476 풀이로 곧 돌아오겠습니다 커밍쑨 ---- 일단 풀면서 LCS LIS 관련 문제임을 알게 되었고 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%E..

티스토리툴바