초보개발자의 작은 끄적임

1520번: 내리막 길 여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으 www.acmicpc.net 풀이 방법 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; import java.util.Queue; import java.util.StringTokenizer; public class Q_1520 { static int N, M; static int[][] array, dp; static..

1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 풀이 방법 처음에는 모든 경우의 수를 1개일 때, 2개일 때, ..., 10개일 때로 나누어서 생각해보았는데 시간복잡도가 O(n^3)이 나와서 의미 없다고 생각했다. 그래서 이 문제는 dp로 밖에 못 푸는구나 하고 깨달았다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public ..

2293번: 동전 1 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. www.acmicpc.net 풀이 방법 점화식을 세우는 건 익숙하지 않아서 정말 어렵다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q_2293 { public static void main(String[] args) throws IOException { BufferedRead..

1932번: 정수 삼각형 첫째 줄에 삼각형의 크기 n(1 ≤ n ≤ 500)이 주어지고, 둘째 줄부터 n+1번째 줄까지 정수 삼각형이 주어진다. www.acmicpc.net 풀이 방법 왼쪽 위의 대각선과 오른쪽 위의 대각선에 존재하는 값을 비교해 큰 값을 더해주는 방식으로 위에서 아래로 가는 방법을 선택했다. 마지막 배열에 존재하는 값들 중에서 가장 큰 값이 최대가 되는 경로에 있는 수의 합이된다. 구현 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Q_1932 { static int n; publ..