kthng

boj 9665 : GMO https://www.acmicpc.net/problem/9665 문제를 잘 못 이해해서 여러 번 틀렸고, 제대로 이해한 후에도 어렵게 생각하여 시간초과를 냈다...사실은 쉬운 문제이다.역시 알고리즘은 열린 사고를 강요한다. ㅎㅎㅎㅎ N*M 만에 풀리는 기초적으로 떠올릴 수 있는 알고리즘으로 해결할 수 있다.돼지 유전자를 사과 유전자가 대체할 수 있으면 사과 유전자로 하고, 사과 유전자로 대체할 수 없으면 돼지 유전자를 이용한다.이 방법으로 사과 유전자의 모든 위치에서 돼지 유전자를 주입할 때의 코스트를 구하고, 그 코스트들 중 최소값을 출력하면 정답.

boj 2450 : 모양정돈 https://www.acmicpc.net/problem/2450 아이디어는 굉장히 간단하다.DP로 먼저 접근하다가 시간이 오래걸렸을 뿐.... 완전탐색으로 (네모, 세모, 원)의 순열을 찾으면 총 6가지인데, 각각 순열에 대하여 최소이동횟수를 구하면 된다.최소 이동 횟수를 생각하는 것이 난 조금 어려웠는데.. (i,j) : i위치에 있는 j의 갯수이렇게 두면(1,2) - (2,1) >= 0 ? (1,2) + (1,3) + (1,2) - (2,1) + (3,2)else (1,2) + (1,3) + (1,3,) - (3,1) + (2,3) 이렇게 된다.풀어서 해석하면 1먼저 다 채우고, 2,3을 채운다는 개념.다른사람의 코드를 보니 (1,2) + (1,3) + max( (2,3..

boj 2792 : LJUBOMORA https://www.acmicpc.net/problem/2792 DP로 풀릴 수 있는가 보느라 한참을 고민했다.하지만 의외로 간단하게 풀릴 수 있었음... [1 ~ 가장 많은 보석 수]에서 이분 탐색으로 찾는다.만약 보석을 적게 나눠준다면 모든 보석을 털 수 없다.보석을 모두 털 수 있는 최소 갯수가 정답. 예제의5 274 이 경우, 2개씩 나눠주면, 2 2 2 1 2 2로 6명이 있어야 하므로 모든 보석을 털 수 없다.3개씩 나눠주면 3 3 1 3 1로 5명에게 털 수 있다.따라서 5명에게 나눠주면 모든 보석을 털 수 있는 최소 보석수는 3개이다. 이 방법으로 해결하면 시간복잡도는 MlogM