알고리즘31 [Greedy] 백준 19639번 - 배틀로얄 일단 정답률이 27%라서 쫄았다 오늘 하루는 이거겠구나 하는 생각으로 시작한다 i번째 줄의 수 Vi가 음수라면, i번째 행동에 −Vi번째 적을 죽인다. i번째 줄의 수 Vi가 양수라면, i번째 행동에 Vi번째 아이템을 먹는다. 준석 제외 플레이어 수 = X 체력 회복 아이템 수 = Y 준석의 처음 및 최대 체력 = M (짝수) 준석이의 체력 잃는 양 그렇게 먹으나 1/2 초과 될때까지 포션들 집어 먹는 것이나 똑같지 않나? -> 그래서 예제에서는 크기 상관없이 1번째(3) 죽이고 2번째(5)죽이고 그랬구나? => 1/2 초과될 때까지 포션 먹는 것으로! 3. 그렇다면 포션 총 회복량 + M 사실상 적들을 치는 순서가 .. 2021. 1. 18. [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 ··· 5 6 7 8 다음
