문제1)
입력)
첫째 줄에 식량창고의 개수 n이 주어집니다.
줄째 줄에 공백을 기준으로 각 식량창고에 저장된 식량의 개수 k가 주어집니다.
출력)
첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하세요
입력 예시)
4
1 3 1 5
출력 예시)
8
시간 제한: 1초 / 메모리 제한: 128MB
문제 풀이)
나는 이렇게 풀어보았는데 답은 나오긴 했다. 초기 값 인 n이 1일때와 2일때 값을 설정하고 점화식에 따라 d[n] 을 n 번째 값의 최대 값 으로 정의 후 n의 값이 없다면 재귀함수를 통해 n-2 번째 값중에 최대 값 + k리스트의 n번째 값을 더해주는 것이다.
보텀 업 문제 풀이)
초기 값인 d[0]과 d[1]을 설정하고 보텀 업 방식인 반복문을 통하여 작은 문제를 통하여 최대 값을 비교하며 찾는 방식이다.
문제 2)
입력)
첫째 줄에 정수 X가 주어집니다. (1 <= x <= 30,000)
출력)
첫째 줄에 연산을 하는 횟수의 최솟값을 출력합니다.
입력 예시)
26
출력 예시)
3
시간 제한: 1초 / 메모리 제한: 128MB
문제 풀이)
그리드 방식으로 푼다면 최적의 해를 구할수 없기때문에 다이나믹 프로그래밍을 통하여 풀수있다. 보텀 업 방식으로 for 문을 통하여 작은 값 부터 d[i] 값에 저장해가며 가장 작은 문제부터 해결하며 큰 문제를 해결 하는 방식이다.
:)