Hello, Freakin world!

www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, �� www.acmicpc.net 백트래킹의 개념을 알고 있다면 풀이 방법을 쉽게 떠올릴 수 있습니다. 위 그림을 보시면 재귀적인 구조를 쉽게 눈치챌 수 있습니다. 재귀 구조를 통해 sum을 구한 다음, 리턴하면서 대소를 비교하며 최대/ 최소를 각각 구해내면 됩니다. 그리고 각 연산자들의 숫자를 백트래킹을 이용해 계산해주면서 연산자 개수 > 0 일 때만 재귀호출 하도록 합니다. 말로 ..

https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 재귀를 이용한 완전 탐색도 통과할 수 있습니다. 입력이 최대 15이므로 2^15가 32768이기 때문에 충분히 통과할 수 있습니다. dp와 완전탐색 각각의 방식이 이 문제에서는 별다른 속도 차이를 보이지 않았습니다. 문제가 단순해서인지 결국 DP를 이용해 푼 방식이 재귀를 이용한 완전탐색을 그저 for문으로 바꾼 것일 뿐이었는데 DP의 정의에 대해 다시 한번 생각해보게 되네요. DP라는게 그저 for문을 이용한 바텀업 방식의 완전탐색일 뿐인 아니지 않나? 라는 생각이 들었습니다. DP의 최적 부분 구조를 찾는데 항상 애를 먹었는데, ..