Do it 알고리즘 코딩테스트 하루코딩 6장 그리디 문제

#16 32 동전의 개수의 최솟값 == 거스름돈을 가장 적은 개수의 지폐로 거슬러 주는 경우의 수

동전의 종류 개수N, 만들고자하는 가격K,  동전 수는 충분

 

가장 가격이 큰 금액의 동전부터 구성하면 된다. // 먼저 그리디로 풀어도 되는지 판단한 후 구현

 

그러나, 반례를 잘 따져봐야 한다.

ex) 135 9

51111 5개

333 3개

 

배수라는 조건이 있으므로 괜찮다. // Ai-1의 배수 Ai

 

오름차순이므로 역순으로 접근해야 가장 가격이 큰 금액부터 접근 가능하다. 가장 가격이 큰 것 부터 순서대로 찾아서 K보다 작은 값 찾기

int count = 0; // 동전의 개수 초기화

for(int i = N-1; i>=0; i--) {

 동전 수 += 목표금액 K/현재 동전의 가치

 K = K % 현재 동전의 가치 // 목표금액 K 업데이트

}

 

#17 36 최솟값을 만드는 괄호 배치 찾기

괄호를 적절하게 배치해 결과가 최소

조건은 일반적인 수식이 되어 오류 없도록 하는 역할

 

그리디 관점에서 생각해보면 쉽게 풀린다.

빼는 수가 클수록 전체 결과가 최소가 된다. 더하는 수가 최소일 수록 결과가 최소가 된다. // 여기서는 더하는 수는 앞에 100으로 고정

 

수식을 문자열로 받아서 "-" 구분자로 분리하면

"100" "40+50+74" " 30+29"

 

또, 이렇게 분리된 문자열을 "+" 구분자로 분리한 뒤, 문자열을 숫자로 변환하여 모두 합한 결과를 리턴

int temp = mySum();

 

if(맨 앞) answer += temp;

else answer -= temp;

 

split() 메소드가 "+"를 잘 인식하지 못하므로 "[+]" 로 표기한다.