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) 단순하게 가지고 있는 현재의 주식을 모두 파는 것이 아니라 원하는 만큼 팔 수 있다는 점에 주목했다. 그런데 조금 생각해보니 미래를 예측할 수 있다는 가정이 있으니 주식의 가격이 내리면 사고, ..

그리디 알고리즘이란? 그리디 알고리즘, 탐욕 기법은 현재 상황에서 가장 좋은 것만을 고르는 문제해결 방법입니다. 그리디 알고리즘은 구현이 쉽다는 장점이 있지만 최적해를 구할 수 있는 경우는 많지 않습니다. 따라서 보통은 근사치 추정을 위해 그리디 알고리즘을 사용하곤 합니다. 일반적으로 코딩테스트에서는 문제를 풀기 위한 적절한 아이디어를 떠올리고, 또 그리디 알고리즘의 해법으로 해결이 가능한지(즉, 매 상황에서 가장 좋은 것을 고르는 방식으로 최적해 도출이 가능한지)에 대한 정당성을 분석하는 능력을 요구합니다. 예를 들어, 다음과 같은 트리구조에서 연결된 부모 노드와 자식 노드의 조합만으로 가장 큰 정수값을 도출해야 한다고 할 때, 그리디 알고리즘은 최적해를 구할 수 있을까요? 그리디 알고리즘은 눈 앞에 ..