[백준] 1932번: 정수 삼각형
📝 문제
처음에는 그래프 탐색과 비슷하게 생각해서 dfs알고리즘으로 풀었다.
하지만 위의 방법으로 풀면 시간초과가 난다.
dfs의 시간복잡도는 정점의 개수(N)에 대하여 O(N^2)이라서 그런 거 같다.
근데 1억에 1초니까 N^2하면 최악의 경우가 250,000인데...
흠,, 왜 시간초과가 나는 걸까?
그래서 다른 풀이법을 고민해보다가 수를 입력 받을 때 바로 DP로 풀면 시간초과를 피할 수 있을 거 같았다.
DP로 풀 때는 입력과 동시에 계산을 하므로 시간복잡도는 O(N)이 된다.
📌 코드
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ1932 {
/**
* dfs로 푸니까 시간초과
* dp로 풀어보자
*/
static int n;
static int[][] tree;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
tree = new int[n][n];
StringTokenizer st;
tree[0][0] = Integer.parseInt(br.readLine());
for(int i = 1; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j <= i; j++){
// prev : tree[i-1][j] or tree[i-1][j-1]
int input = Integer.parseInt(st.nextToken());
// col : 0
if(j == 0){
tree[i][j] = tree[i-1][j] + input;
}
else if(j == i){
tree[i][j] = tree[i-1][j-1] + input;
}
else{
tree[i][j] = Math.max(tree[i-1][j], tree[i-1][j-1]) + input;
}
}
}
for(int i : tree[n-1]){
answer = Math.max(answer, i);
}
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 1932번: 정수 삼각형), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@paulus0617/boj1932
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
package Baekjoon;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BOJ1932 {
/**
* dfs로 푸니까 시간초과
* dp로 풀어보자
*/
static int n;
static int[][] tree;
static int answer = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
n = Integer.parseInt(br.readLine());
tree = new int[n][n];
StringTokenizer st;
tree[0][0] = Integer.parseInt(br.readLine());
for(int i = 1; i < n; i++){
st = new StringTokenizer(br.readLine());
for(int j = 0; j <= i; j++){
// prev : tree[i-1][j] or tree[i-1][j-1]
int input = Integer.parseInt(st.nextToken());
// col : 0
if(j == 0){
tree[i][j] = tree[i-1][j] + input;
}
else if(j == i){
tree[i][j] = tree[i-1][j-1] + input;
}
else{
tree[i][j] = Math.max(tree[i-1][j], tree[i-1][j-1]) + input;
}
}
}
for(int i : tree[n-1]){
answer = Math.max(answer, i);
}
System.out.println(answer);
}
}
Author And Source
이 문제에 관하여([백준] 1932번: 정수 삼각형), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@paulus0617/boj1932저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)