kthng

boj 5623 : SUME https://www.acmicpc.net/problem/5623 단순한 수학문제인 것 같다.a0을 먼저 구하고 a1,a2...a(n-1)까지 구하면 됨. n = 2일 경우가 제일 문제인데, n = 2일 경우는 유일한 수열을 구할 수 없다.하지만20 22 0이 경우는 1 1로 유일하게 구할 수 있어서n = 2가 input으로 주어지면 1 1 을 출력해준다.(문제에서 유일한 경우만 주어지고, ai는 자연수라고 하였기 때문)

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가 빌 때까지 반복하면 각각 노드까지의 최대값을 구할 수 있다.

boj 1700 : 멀티탭 스케쥴링 가장 나중에 쓰이는 플러그를 뽑아주면 된다.직관적으론 이해되는데 어떻게 증명할 수 있을까?... stl map을 이용하여 nlogk로 해결하였지만 코드의 갯수 최대 100, 가전기기 갯수 최대 100이어서 티는 안나는듯 ㅜㅜ map사용 시 map.size()에 뭔가 문제가 있는 듯 하다.설마 stl에 버그가 있겠어? 라는 생각에 한참을 디버깅한듯 ㅜㅜㅜsize를 직접 구현하면 가볍게 AC지만 map.size()를 이용하면 size가 바로바로 초기화가 안돼서 다른 값을 내는듯. 아마 iterator와 함께 써주면 문제가 생기는 버그가 있는 것 같다.기억해둬야할듯!

boj 9526 : Bus https://www.acmicpc.net/problem/9546 오늘의 마지막문제!!! 마지막문제는 쉬운문제로.. 1. a[0] = 02. a[i] = 2 * (a[i - 1] + 1) 정답은 a[k]/2 를 출력.

boj 2696 : Running Median https://www.acmicpc.net/problem/2696 총 3가지 방법으로 해보았다. 첫번째 : 가장 단순한 방법으로 sorting + 중간값 출력...n * n * logn역시나 시간초과 ㅎㅎ 두번째 :selection 알고리즘.예전에 코드를 직접 짜보았었던게 생각나서 해보았다.첫번째 방법이 n * n * logn 이라면 이방법은 n * n만에 가능.직접 짜는것보다 nth_element를 이용..ㅎㅎㅎ 44ms로 AC 세번째 : left, right 2개의 힙 이용.a[i]가 mid보다 클 경우 right에 push, 작거나 같은경우 left에 push.(작거나 같을 경우나 크거나 같을 경우는 따로 고려해주지 않아도 된다.)홀수번째마다 3가지 경..

boj 2698 : Adjacent Bit Counts https://www.acmicpc.net/problem/2698 생각한 시간은 길었지만 점화식은 간단하게 나온다. 1. A[n][k][e] : e로 끝나고 k개의 인접비트를 가지는 길이 n인 string의 수2. A[1][0][0] = 1, A[1][0][1] = 13-1. A[n][k][0] = A[n - 1][k][1] + A[n - 1][k][0]3-2. A[n][k][1] = A[n - 1][k][0] + A[n - 1][k - 1][1]

boj 9518 : MISA https://www.acmicpc.net/problem/9518 (Mirko의 최대 악수 수) + (Mirko없을 때의 악수 수)를 출력해주면 된다.(Mirko 없을 때의 악수 수)는 sum(각 사람들이 할 수 있는 악수 수)/2

boj 2487 : 섞기 수열 https://www.acmicpc.net/problem/2487 각 cycle 길이의 lcm을 출력해주면 된다.예를들어 섞기수열이 3 2 5 6 1 4인 경우cycle(1) = 3 (1->3->5->1),cycle(2) = 1 (2->2)cycle(3) = 3cycle(4) = 2 (4->6->4)cycle(5) = 3cycle(6) = 2이므로 lcm(cycle(1),cycle(2), ..., cycle(6))인 6을 출력해주면 정답.각각 숫자에 대한 cycle 수를 구하는 것 보단 1의 cycle을 구하고 cycle의 경로에 있는 1,3,5의 cycle 수도 모두 같은 값으로 해주면 훨씬 빠르다.