kthng

boj 5624 : DOBRI https://www.acmicpc.net/problem/5624 삼성 코드그라운드의 좋은수 라는 문제와 유사하다.N의 범위가 [-100000,100000]이라는 데서 힌트를 얻을 수 있다.i번째 숫자가 세 수의 합으로 이루어져있는지 확인하기 위해서 일반적으로 코딩을 한다면 N^3으로 가뿐하게 시간초과가 나지만,(i번째 숫자) - (i보다 먼저 오는 숫자)가 두 수의 합으로 이루어져있는지 확인하는 방법으로 코딩을하면 N^2만에 해결할 수 있다.이 방법으로 해주기 위해 두 수의 합으로 이루어져있는지 확인하는 -100000~100000범위의 bool 배열을 이용한다.

boj 13141 : Ignition https://www.acmicpc.net/problem/13141 참여했던 대회인 펑션컵에서 출제되었던 문제.dijkstra알고리즘을 이용하여 각 node까지 타는데 걸리는 최소시간을 구하고,이를 이용하여 edge가 타는 시간을 구하였다.일단 node가 탈 때까지 걸리는 시간을 구하고 나면 edge가 타는 시간은 조금만 생각해보면 구할 수 있다.각각 시작점을 달리하여 dijkstra알고리즘을 돌렸기 때문에 시간복잡도는 NElogE.다른사람들은 플로이드 알고리즘을 돌린 사람도 있는데, 이렇게해주면 N^3으로 E가 N^2에 가깝지 않으면 좀더 빠른것같다.

boj 1939 : 중량제한 https://www.acmicpc.net/problem/1939 DFS+메모이제이션으로 어떻게 풀 수 있을지 고민하다가그냥 BFS로 풀어제꼈다.일반적인 BFS로 해결 가능하다. current번째 노드까지의 최대 무게를 flow[current]라 하면, current노드와 연결된 next 노드의 의 값, nextCost는 min(flow[current],edge(current,next) )이다. 최종적으로 초기화된 flow[next]값보다 nextcost값이 작다면 next와 nextcost의 쌍을 queue에 넣어준다.최종적으로 queue가 빌 때까지 반복하면 각각 노드까지의 최대값을 구할 수 있다.