kthng

boj 2688 : Non-Decreasing Digits https://www.acmicpc.net/problem/2688 DP로 간단하게 해결 가능하다. 1. a[i][j] : i번째 j로 끝나는 경우의 수2. a[i][j] = sum{ a[i - 1][0] ~ a[i - 1][j] }

boj 2469 : 사다리타기 https://www.acmicpc.net/problem/2469 사다리의 위에서 부터 blank line을 만날 때까지 내려가고, 아래서부터 blank line을 만달 때까지 올라온 string을 각각 a,b라고 하면 1. a[i] = b[i] 일 경우 * 표시,2. a[i] = b[i + 1] && a[i + 1] = b[i] 이고 이전에 '-' 표시를 하지 않았다면 '-'표시3. 1,2 둘다 아닌 경우는 만족하는 사다리를 만들 수 없다.

boj 10159 : 저울 https://www.acmicpc.net/problem/10159 플로이드 알고리즘과 유사한 방법으로도 풀 수 있다. a b의 경로가 있는가? 로 변환된다.a b 이고 b -> c일 때 a -> b -> c 이므로 a -> c 이다. 1. a와 b의 관계를 구할 수 있는가?2. a b 이거나 b -> a 인가? 1,2,3은 동치이므로 a와 b의 관계를 구할수 있는가? 라는 질문은a -> b의 경로 혹은 b -> a의 경로가 있는가? 라는 질문으로 변형하여 floyd 알고리즘으로 푼다. 시간 복잡도는 n^3

boj 2602 : 돌 다리 건너기 https://www.acmicpc.net/problem/2602 간단한 DP로 해결 가능하다. 1. 순서대로 방문해야하는 문자열을 s, 천사다리를 ss[0], 악마다리를 ss[1]이라 두고,a(i, j, k)를 i개의 문자열을 이용했을 때 j다리 k번째 위치까지의 경우의 수로 두면 2. a(i, j, k) = sum{ a(i-1, !j, 1~k) } ( ss[j][k] = s[i] 일 때) 이와같이 점화식을 세우면 간단하게 답을 출력할 수 있다.

boj 5397 : Keylogger https://www.acmicpc.net/problem/5397 2개의 stack을 이용해서 간단하게 해결 할 수 있다.커서가 현재 위치하고 있는 곳을 기준으로 왼쪽 문자열은 left stack에, 오른쪽 문자열은 right stack에 넣어준다. 의 경우 반대로 right stack에서 pop하여 left stack에 push.-의 경우 left stack을 pop.charactor의 경우 left stack에 push. 위의 4가지 연산으로 모두 해결 가능하다.

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

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으로 해결하는 방법도 가능하다.