백준 11399 (1) 썸네일형 리스트형 그리디: 백준 11399 파이썬 문제: https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 풀이: 이 문제는 단순히 돈을 인출하는데 걸린 시간 P가 저장되어있는 배열을 정렬하고, 누적합을 구하면 되는 문제이다. for문을 두 번 사용해서도 풀 수 있지만, 시간 복잡도를 줄이기 위해 for문을 한 번만 쓰는 방법을 생각하다가 다이나믹 프로그래밍 기법(동적 계획법)을 떠올렸다. 이 문제는 다이나믹 프로그래밍의 조건인 1. 큰 문제를 작은 문제로 나눌 수 있는가, 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰.. 이전 1 다음