kthng

boj 2624 : 동전 바꿔주기 https://www.acmicpc.net/problem/2624 이 문제 또한 전형적인 DP문제이다.나에게는 조금 생소했던... 하지만 이것저것 검색해보니 이문제 또한 전형적인 DP문제라는 것을 알 수 있었다. 이 문제가 만약 동전의 갯수가 주어지지 않았다면 바로 DP로 접근해서 풀었겠지만, 동전의 갯수가 주어져 있으면 DP로 접근하면 해결할 수 없을 것만 같다.시간복잡도가 엄청 높기 때문이다. (약 T*k*n) 그렇다면 그냥 시간초과 나는게 아닌가? 일단은 풀린다. 방법은 i번째의 동전으로 table을 채워가는 것. 초기 세팅은 0원의 경우의 수를 1로 두고 table을 채운다. 1. a[cost][i] i 번째 동전까지의 cost의 경우의 수2. Pi, ni : i..

boj 1149 : RGB거리 https://www.acmicpc.net/problem/1149 DP로 해결한다. 1. dp[i][j] : i번째의 집을 j로 칠했을 때 1~i번째 집까지의 최소비용2. dp[i + 1][j] = min{ dp[i][k] } + cost[i + 1][j]; ( j != k )

boj 9657 : 돌 게임 3 https://www.acmicpc.net/problem/9657 재미있는 문제다.어려워보이지만 굉장히 간단한 코드를 작성할 수 있다. 위의 표를보면, 돌의 갯수가 2개일 때는 cy가 이긴다.7번째와 9번째도 cy가 이긴다.공통점은 a[i - 4] , a[i - 3], a[i - 1]이 모두 sk가 이길 경우 a[i] 는 cy가 이긴다는 것.왜그럴까?cy가 이긴다는 것은 후수가 이긴다는 얘기다. 마찬가지로 sk가 이기는 경우는 선수가 이긴다는 것이다.i 개일 때 sk가 이기려면, sk가 후수를 내주었을 때, 즉 i - 4, i -3, i - 1 셋중 하나가 후수가 무조건 이기는 경우가 있어야만 가능하다. 8의 경우를 보면 8 - 4 = 4 : sk, 8 - 3 = 5: s..

boj 11052 : 붕어빵 판매하기 https://www.acmicpc.net/problem/11052 DP로 해결할 수 있는 문제이다.1. dp[i] : i개를 판매할 때 최대의 가격2. a[i] : i개 세트의 가격위와 같이 두면, 3. dp[i] = max{ dp[i - k] + a[k] } ( k = 1 ~ i - 1 ) 위와같이 점화식을 구성하여 해결한다.

boj 5622 : BAKA(다이얼) https://www.acmicpc.net/problem/5622 아스키코드 배열로 해결하였다.a['A'] = 2, a['B'] = 2, a['C'] = 2 a['D'] = 3,... a['Z'] = 10. for i = 0 ~ str_size - 1sum += a[str[i]];

boj 1298 : 노트북의 주인을 찾아서boj 2188 : 축사 배정 https://www.acmicpc.net/problem/1298https://www.acmicpc.net/problem/2188 두 문제 모두 이분매칭의 1번문제이다.이분매칭 문제를 모든 경우를 고려할 경우 시간복잡도는 N!로 N이 웬만큼 작지 않으면 해결할 수 없다."네트워크플로우 -> 이분매칭" 으로 이어지는 공부 과정을 거쳐야 풀수 있는 문제이다. 이분매칭 문제는 위와같이 단순한 형태의 네트워크 플로우 모형으로 바뀌고, 동시에 "가장 매칭쌍이 많으면 몇개일까?" 라는 질문은 "source에서 sink로 최대 얼마나 흘려줄 수 있을까?" 라는 질문으로 바뀐다. 이후 포드 퍼커슨 알고리즘을 이용하여 네트워크 플로우의 최대 흐름을 ..

boj 2672 : 여러 직사각형의 전체 면적 구하기 https://www.acmicpc.net/problem/2672 풀었던 문제 중 제일 많이 틀렸습니다!! 인 것 같다.ㅜㅜ... 처음 접근은1. 사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다. 이렇게였는데, 틀렸다.위와같은 방법으로 접근하려면 1.사각형의 넓이를 다 더한다.2. 두 사각형이 겹치는 넓이를 뺀다.3. 세 사각형이 겹치는 넓이를 더한다.4. 네 사각형이 겹치는 넓이를 뺀다.5. 다섯 사각형이 겹치는 넓이를 더한다..... 이와같이 접근해야하므로 시간복잡도를 감당할 수 없을 것 같아 포기. 생각을 거듭하다보면, 이런 생각을 떠올릴 수 있다. 위와같은 사각형이 주어졌을 때, 위와같이 영역을 모두 쪼갠다.이후 각 영역이 사각..

boj 1701 : editor(cube editor) https://www.acmicpc.net/problem/1701 내가 풀어낸 해법은 간단하다.하지만 좀더 빠르게 풀려면 뭔가가 필요한 것같다.. 접미사 배열에서 중복제거라던가..KMP라던가 ㅜㅜ 일단 내가 풀어낸 방법은1. 접미사 배열을 모두 뽑아낸다.2. 접미사 배열을 정렬한다.3. 인접한 접미사의 최대 매칭 길이를 구한다.4. 그 길이의 최대값을 출력한다. 2번->3번으로 넘어가는게 생각이 약간 필요하다.생각의 흐름은1. 접미사의 공통된 앞부분은 문자열의 공통된 부분문자열이다.2. 접미사는 정렬되어있다.3. i번째, i+1번째 접미사의 최장부분매칭길이를 구하면 공통된 부분문자열의 최대길이이다. 떠올릴 수 있는 간단한 방법이니만큼 어딘가에 개선의..

boj 2841: GITARA(외계인의 기타연주) https://www.acmicpc.net/problem/2841 문제를 이해하기가 힘들지만, 이해만 하면 풀 수 있는 아이디어를 간단히 떠올릴 수 있다. 7개의 stack을 이용하면 된다.stack의 top이 눌러야할 플렛보다 클경우 모두 pop해주고 눌러야할 플렛을 push해주면 해결된다. 7개의 줄은 모두 독립적으로 처리하면 된다. pop한 횟수와 stack에 push한 횟수만큼이 손가락을 움직이는 횟수이다.

boj 2934 : CVJETICI(LRH 식물) https://www.acmicpc.net/problem/2934 펜윅트리를 이용하여 해결할 수있다.울타리 기둥의 좌표가 주어졌을 때 그 울타리를 가로지르는 팬스의 갯수를 구하는 데 펜윅트리를 이용한다. 먼저 펜윅트리는 구간의 합을 빠르게 구하는 데 쓰인다. 이를 응용하면 좌표가 주어졌을 때 '그 좌표를 포함하는 구간들' 의 갯수를 빠르게 구할 수 있다. 울타리의 left, right가 주어질 때 add(left + 1,1), add(right,-1)이렇게 하면 해당구간을 가로지르는 펜스의 갯수를 누적할 수 있다. 이렇게 하면 sum연산으로 누적되어있는 울타리의 수를 알아낼 수 있다.그렇다면 남은건 이미 피어있는 꽃에 대한 처리는 어떻게해줘야하는가? 에대..