Baekjoon 4929 수열 걷기 JAVA

4929번: 수열 걷기

문제

길이가 유한하고, 오름차순 순서로 되어있는 두 수열이 주어진다. 두 수열에 공통으로 들어있는 원소는 교차점으로 생각할 수 있다.

아래는 두 수열과 교차점은 굵게 나타낸 것이다.

수열 1 = 3 5 7 9 20 25 30 40 55 56 57 60 62

수열 2 = 1 4 7 11 14 25 44 47 55 57 100

이 두 수열은 다음과 같이 걸을 수 있다.

1. 두 수열중 하나의 첫 번째 원소에서 걷기를 시작한다. 걷는 것은 앞으로만 걸을 수 있다.
2. 교차점에 도착했을 때는, 현재 수열에서 계속 걸을지, 다른 수열로 갈아탈지 결정할 수 있다.

방문한 수의 합이 최대가 되는 경로를 구하는 프로그램을 작성하시오. 위의 예에서 3, 5, 7, 9, 20, 25, 44, 47, 55, 56, 57, 60, 62와 같이 걷는다면 합이 450으로 최대가 된다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 두 줄로 이루어져 있다.

각 줄의 첫 번째 수는 수열의 길이이다. 그 다음에는 수열의 원소가 순서대로 주어진다. 수열의 길이는 1이상이고, 10,000을 넘지 않는다. 수열에 들어있는 모든 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.

입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 얻을 수 있는 최대 합을 출력한다.

풀이

수열 1에서 시작하는 경우과 수열 2에서 시작하는 경우 두가지를 생각해서 값을 만들어 나간다.

극단적으로 수열 1이 "1 2 3 4 5 6 7 8 9 15", 수열 2가 "9 100"의 경우 최대 값을 1 2 3 4 5 6 7 8 9 100이 최대의 경우가 되기에 값을 하나씩 증가시키면서 교차점이 생길때 이전부터 교차점이 생기는 값 이전의 최대값을 이용하여 추가적으로 지나가는 값을 찾아준다.

자세한 것은 코드를 참고

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		while(true) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int l1 = Integer.parseInt(st.nextToken());
			int [] arr=new int [l1];
			for(int i=0;i<l1;i++)
				arr[i]=Integer.parseInt(st.nextToken());
			if(l1==0)	// 마지막줄에 입력받는 값이 0하나면 종료
				break;
			st = new StringTokenizer(br.readLine());
			int l2 = Integer.parseInt(st.nextToken());
			int[] brr = new int[l2];
			for(int i=0;i<l2;i++)
				brr[i]=Integer.parseInt(st.nextToken());
			int t1=0, t2=0, sum=0, i=0, j=0;
			// t1은 수열 1을 통해서 만들어지는 값, t2는 수열 2를 통해서 만들어 지는 값
			// sum은 최종으로 출력되는 값, i는 수열 1의 index, j는 수열 2의 index
			while(i<l1 && j<l2) {
				if(arr[i]==brr[j]) {	// 교차점에 위치하게 되면 
					sum+=Math.max(t1, t2);// 수열 1을 통한 값과 수열2를 통한 값 중 큰 값을 선택
					sum+=arr[i];	// 교차점 위치는 저장되지 않았기에 교차점 값을 추가
					t1=t2=0;	// 큰 값을 선택했기에, 더해지는 temp값을 초기화
					i++;
					j++;
				}
				else if(arr[i]<brr[j] && i<l1)	// i가 수열1의 범위 안에 있고, 값이 수열2의 값보다 작다면 수열 1을 증가
					t1+=arr[i++];
				else if(arr[i]>brr[j] && j<l2)	// j가 수열2의 범위 안에 있고, 값이 수열1의 값보다 작다면 수열 2을 증가
					t2+=brr[j++];
			}
			for(;i<l1;i++)	// while의 조건이 i가 l1보다 작고, j가 l2보다 작은 것이기 때문에 i와 j의 값으로 종료되었다면 남은 범위를 탐색해서 마지막 경로 까지의 큰 값을 찾음
				t1+=arr[i];
			for(;j<l2;j++)
				t2+=brr[j];
			sum+=Math.max(t1, t2);	// 마지막 경로의 최대 값을 저장
			sb.append(sum+"\n");
		}
		System.out.println(sb.toString());
	}
}