BOJ2118 두개의 탑*R

이진탐색, 투 포인터로 다시 풀어보기

 

이진탐색 NlogN

투 포인터 N

누적합 N^2

 

https://www.acmicpc.net/problem/2118

2118번: 두 개의 탑

환형구조에서 반대쪽으로의 거리를 구할려면 전체 거리 - 순방향 거리를 하면 된다.

투포인터 문제이지만 나는 N2 복잡도인 누적합으로 해결하였다.

 

환형구조의 경우 선형자료형에 저장하기 위해 모듈러(%)를 사용하여 인덱스를 관리해 주어야 한다.

상황에 따라 그냥 배열을 두배로 늘리고 모듈러를 사용하지 않는 것도 방법이다.

 

import java.util.*;
import java.io.*;
public class Main
{

	public static void main(String[] args) throws IOException {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    int n = Integer.parseInt(br.readLine());
	    int[]  distances = new int[n];
	    
        int distance_sum = 0;	    
	    for(int i=0; i<n;i++){
	        distances[i]= Integer.parseInt(br.readLine());
	        distance_sum+=distances[i];
	    }
	    

        int[] acc = new int[n+1];
	    acc[0]=0;
	    
	    for(int i=1;i<n+1;i++){
	        acc[i] = acc[i-1] + distances[i-1];
	    }
	    
	    int ans=0;
	    for(int i=0; i<n; i++){
	        for(int j=0; j<n; j++){
	            int dist = Math.min(distance_sum-(acc[i+1]-acc[j]),acc[i+1]-acc[j]);
	            ans = Math.max(dist,ans);    
	        }
	        
	    }

	    
	    
	  
	    System.out.println(ans);
	    

	}
}

 

 

투 포인터를 이용한 코드

시계방향보다 반시계방향이 커지는 순간에서 while문 나감 -> 최대 값임 그때가

그리고 다음 반복문은 시작탑만 옮김 왜냐하면 도착탑까지는 무조건 가능하기 때문(이전반복문에서의 최대값이니 다음 반복문에서도 무조건 가능함)

import java.util.Scanner;

class Main
{
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int[] distance = new int[N];
        int distanceSum = 0;
        for (int i = 0; i < N; i++) {
            distance[i] = sc.nextInt();
            distanceSum += distance[i];
        }

        int pairIndex = 1;
        int leftDistance = distance[0];
        int rightDistance = distanceSum - distance[0];
        int maxDistance = Math.min(leftDistance, rightDistance);
        for (int i = 0; i < N; i++) {
            while (leftDistance < rightDistance) {
                leftDistance += distance[pairIndex];
                rightDistance -= distance[pairIndex];
                pairIndex = (pairIndex + 1) % N;
            }
            maxDistance = Math.max(maxDistance, Math.min(leftDistance, rightDistance));

            leftDistance -= distance[i];
            rightDistance += distance[i];
        }
        System.out.println(maxDistance);
    }
}