kthng

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

boj 2981 : GRANICA https://www.acmicpc.net/problem/2981 고민을 좀 했던 문제이다. Aij를 ai와 aj(i != j)의 차이라고 할때모든 Aij의 공약수를 출력해주면 된다. 모든 Aij의 공약수는, a가 정렬되어있을 때, ai - a(i-1)의 공약수이다.( gcd(a,b) = gcd(a + b, b) ) 답은 공약수들을 정렬하여 출력하면 된다.(영문은 any order라고 되어있는데 ㅜㅜㅜ...)

boj 4198 : Trainsorting https://www.acmicpc.net/problem/4198 증가 부분수열, 감소 부분수열 을 이용하여 해결한다.(n번째부터 시작하는 증가부분수열의 갯수) + (n번째부터 시작하는 감소부분수열의 갯수) - 1 의 최대값이 정렬된 train car의 최대 갯수.시간복잡도는 n^2으로 하여 간단하게 풀었지만 nlogn으로 해결하는 방법도 가능하다.

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 를 출력.