kthng

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로 최대 얼마나 흘려줄 수 있을까?" 라는 질문으로 바뀐다. 이후 포드 퍼커슨 알고리즘을 이용하여 네트워크 플로우의 최대 흐름을 ..