https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 설명 DP를 활용한 기본 문제이다. DP가 늘 그렇듯이 반복되는 규칙을 찾아내고 점화식을 구하면 된다. 이 문제의 경우 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구해야 한다. 단, 수는 한 개 이상 선택해야 한다. 예제 입력 1을 가지고 보도록 하자. 앞에서부터 구해보자. 먼저 수를 단 한 개 이상 선택해야 한다고 했으므로 현재 최댓값은 10으로 하자. 그 다음 수인 -4와 더..

https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 설명 정수 X에 사용할 수 있는 연산은 다음 세 가지다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절이 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 구하시오. 풀이 방법 - DP DP 기본 문제로 유명한 문제이다. N = 6 이라고 가정해보자. 이 경우 호출되는 함수의 구조는 다음과 같을 것이다. f(3), f(2), f(1) 처럼 같은 연산이 계속 반복되는 것을 볼 수 있다...

https://www.acmicpc.net/problem/1520 1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 문제 설명 첫 칸에서 마지막 칸까지 갈 수 있는 모든 경로의 수를 구하면 된다. 단, 항상 높이가 더 낮은 지점으로만 이동한다. 풀이 방법 1. DFS -> 시간 초과 보자마자 DFS로 풀면 되겠다고 생각했고 바로 코딩에 들어갔다. 코딩하면서 이게 왜 정답률이 27%밖에 안 되지? 생각했었는데 왜 그런지 코드를 제출해보고 알게 되었다. private static void dfs(int x, int y)..