Itscool

문제 접근 탐욕적 기법의 대표문제로 볼 수 있는 동전 문제이다. 예전에 풀었던 문제라 수월하게 풀었다. 가장 값이 비싼 동전부터 사용해서 전체 금액을 모두 차감하는 식으로 구성하면 된다. import sys n, k = map(int, sys.stdin.readline().split()) coins = [] for i in range(n): coin = int(sys.stdin.readline()) coins.append(coin) i = 0 cnt = 0 while k: big_coin = coins[-(1 + i)] cnt += k // big_coin k = k % big_coin i += 1 print(cnt)

문제접근 이 문제도 회의실 배정과 마찬가지로 그리디 접근 방법으로 풀어야 하기 때문에 명쾌한 테스트 케이스 증명이 아닌 그럴듯한 가설을 세우고 코드를 돌려보며 검증하는 방식으로 접근해야 했다. 회의실 문제와 다르게 시간순으로 정렬된 배열이기에 멋대로 배열의 순서를 바꿨다가는 대참사가 일어날 것 같아 정렬은 사용하지 않았다. 시간 제한은 5초지만 테스트케이스 배열의 길이가 (2 ≤ N ≤ 1,000,000) 라 시간이 넉넉하다고도 볼 수 없었다. 우선 1) 미래의 가격을 예측할 수 있다는 가정 하에 거래하고, 2) 단순하게 가지고 있는 현재의 주식을 모두 파는 것이 아니라 원하는 만큼 팔 수 있다는 점에 주목했다. 그런데 조금 생각해보니 미래를 예측할 수 있다는 가정이 있으니 주식의 가격이 내리면 사고, ..