greedy2 [Greedy] 백준 11047번 - 동전 0 동전을 최대한 적게 이용하려면 큰 값의 동전부터 넣어보아야 한다. 예를 들어 6500원을 만들어야 하고 1000원이 가장 큰 돈 단위라면 1000원부터 6장 넣고 그다음에 남은 500원을 처리하는 것이 더 효율적이다 하지만! 큰 단위의 동전을 넣을 수 있는 만큼 넣었는데 나머지 돈 단위로 해결할 수 없는 애매한 잔액이 남았다면? 그렇다면 한단계 전으로 돌아가서 뺀 다음에 다시 진행 Case 1) 선택한 동전으로 차감할 수 있는 경우 선택한 동전이 K보다 작아야 한다 Case 2) 선택한 동전으로 차감 불가한 경우 다음 작은 동전으로 넘어간다 애초에!!!! Case 1만 남기기 위해 사전에 값을 넣을 때 K보다 큰 수는 vector에 넣지 않는다 최대로 차감할수 있는 동전의 개수를 아는 법 : 남은 돈 /.. 2021. 1. 18. [Greedy] 백준 1080번 - 행렬 그리디.. 어렵고 어렵다 난 일단 문제 읽고 뭔 소리지 싶었다.. 문제부터 막혔다 일단 3 X 3 연산에 대해 생각해보았다 총 (M-3) X (N-3)의 연산이 이루어진다는 것인데...! 매번 연산 하나 할때 마다 행렬 B와 비교해서 최소를 찾는다? 문제점. 어디부분을 연산부터 해야 최소 횟수를 찾을 수 있는것인가 순서대로 하면 최소값 못찾을 거 같고 심지어 B 행렬로 만들어 낼 수 있음에도 못 만들 가능성도 있다 그렇다면???? A 와 B가 다른 부분만 inverse 연산 해주면 된다! 그럼 다른 A와 B가 다른 부분을 표시하는 임시 행렬 tmp를 만들어준다 그럼 이제 tmp 행렬에서 1인 부분만 파악을 해서 그 부분을 기준 삼아 3x3 연산을 실행해 주면 된다 CASE 0 ) 행렬이 같은 경우 사전에.. 2021. 1. 12. 이전 1 다음
