이 문제는 제일 처음 삼각형의 층수인 n을 주고,
각각의 노드에 따라 더해서 제일 큰 값을 구하는 문제이다.
따라서, 입력 받은 값들을 배열에 깔끔하게 저장하기 위해
n에 따른 경우의 수를 구하는 checknum 메서드를 먼저
생성하여 값을 구하였고, 이후 calc 메서드를 생성하여 값을 구하였다.
package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Ox13_Q3_1 {
static boolean visited[];
static int n;
static int count;
static Integer maxNum[];
// 백준 1932 S1
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
n = Integer.parseInt(br.readLine());
int checknum = checknum(n);
visited = new boolean[checknum];
List<Integer> arrList = new ArrayList<>();
maxNum = new Integer[checknum];
int dept = 2;
// 값 받기
for(int i = 0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<=i; j++) {
arrList.add(Integer.parseInt(st.nextToken()));
}
}
calc(dept,checknum,arrList);
}
// 총 공간 체크
public static int checknum(int n) {
int sum = 0;
for(int i=1 ; i<=n; i++) {
sum+= i;
}
return sum;
}
public static void calc(int dept, int checknum, List<Integer> arrList) {
maxNum[0] = arrList.get(0); // 첫 번째 값 세팅
int cnt = 1;
for(int i = 1; i<n; i++) { // n개의 층
for(int j = 0; j<dept; j++) {
// 제일 왼쪽, 제일 끝
if(j == 0 || j == dept-1) {
maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
}
else {
maxNum[cnt]
= Math.max( maxNum[cnt-dept] + arrList.get(cnt), maxNum[cnt-dept+1] + arrList.get(cnt));
}
cnt++;
}
dept++;
}// for fin
for(Integer i : maxNum) {
System.out.print(i + " ");
}
System.out.println();
List <Integer> maxList = Arrays.asList(maxNum);
System.out.println(Collections.max(maxList));
}
}
결과값을보면
근데 입력받은 숫자 만큼 return은 되었으나. 이상하게 더해진다.
삼각형 기준 왼쪽 끝과 오른쪽 끝을 묶었기에 이상하게 나온 것 같아 이부분을 수정해주었다.
package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Ox13_Q3_2 {
static int n;
static Integer maxNum[];
// 백준 1932 S1
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
n = Integer.parseInt(br.readLine());
int checknum = checknum(n);
System.out.println(checknum);
List<Integer> arrList = new ArrayList<>();
maxNum = new Integer[checknum];
int dept = 2;
// 값 받기
// for(int i = 0; i<n; i++) {
// st = new StringTokenizer(br.readLine());
// for(int j = 0; j<=i; j++) {
// arrList.add(Integer.parseInt(st.nextToken()));
// }
// }
//
calc(dept,checknum,arrList);
}
// 총 공간 체크
public static int checknum(int n) {
int sum = 0;
for(int i=1 ; i<=n; i++) {
sum+= i;
}
return sum;
}
public static void calc(int dept, int checknum, List<Integer> arrList) {
maxNum[0] = arrList.get(0); // 첫 번째 값 세팅
int cnt = 1;
for(int i = 1; i<n; i++) { // n개의 층
for(int j = 0; j<dept; j++) {
// 제일 왼쪽, 제일 끝
if(j == 0) {
maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
}else if(j == dept-1) {
maxNum[cnt] = maxNum[cnt-dept] + arrList.get(cnt);
}
else {
maxNum[cnt]
= Math.max( maxNum[cnt-dept] + arrList.get(cnt), maxNum[cnt-dept+1] + arrList.get(cnt));
}
cnt++;
}
dept++;
}// for fin
for(Integer i : maxNum) {
System.out.print(i + " ");
}
System.out.println();
List <Integer> maxList = Arrays.asList(maxNum);
System.out.println(Collections.max(maxList));
}
}
여기선 잘한 것 같은데 오류가 났다.
생각해보니 삼각형의 크기가 500, 수의 경우 9999까지 이므로 합계 같은 경우 Integer을 벗어날 가능성이 높다고 생각했다. 따라서, 누적된 값을 저장해주는 maxNum 의 타입을 Integer에서 Long으로 바꿔주었다.
package test13;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Ox13_Q3_3 {
static int n;
static long maxNum[];
// 백준 1932 S1
public static void main(String [] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st ;
n = Integer.parseInt(br.readLine());
int checknum = checknum(n);
List<Integer> arrList = new ArrayList<>();
maxNum = new long[checknum];
int dept = 2;
// 값 받기
for(int i = 0; i<n; i++) {
st = new StringTokenizer(br.readLine());
for(int j = 0; j<=i; j++) {
arrList.add(Integer.parseInt(st.nextToken()));
}
}
calc(dept,checknum,arrList);
}
// 총 공간 체크
public static int checknum(int n) {
int sum = 0;
for(int i=1 ; i<=n; i++) {
sum+= i;
}
return sum;
}
public static void calc(int dept, int checknum, List<Integer> arrList) {
maxNum[0] = (long) arrList.get(0); // 첫 번째 값 세팅
int cnt = 1;
for(int i = 1; i<n; i++) { // n개의 층
for(int j = 0; j<dept; j++) {
// 계속 작은 삼각형을 그리면서 비교하는 방식으로 이해하면 편하다.
if(j == 0) { // 삼각형의 왼쪽이 해당 행에서 첫 번째인 경우, 가운데 값 + 현재값
maxNum[cnt] = maxNum[cnt-dept+1] + arrList.get(cnt);
}else if(j == dept-1) {// 삼각형의 오른쪽이 해당 행에서 마지막인 경우, 가운데 값 + 현재값
maxNum[cnt] = maxNum[cnt-dept] + arrList.get(cnt);
}
else {// 현재값 기준 11시방향, 1시방향 값 서로 비교
maxNum[cnt]
= Math.max( maxNum[cnt-dept] + arrList.get(cnt), maxNum[cnt-dept+1] + arrList.get(cnt));
}
cnt++;
}
dept++;
}// for fin
// 경우에 따라 int의 한계치를 넘을 수도 있으므로 long으로 세팅
long max = Arrays.stream(maxNum).max().getAsLong();
System.out.println(max);
}// calc fin
}
굿
성장중