14501 퇴사

내용 피드백 : 

1. 연관된 2개의 변수배열을 다룰때

클래스 객체 <  1차원 배열 이 더 빠르다. (코딩도 빠르게 할 수 있다.)

 

2. 모든 연산과 처리 과정을 if문을 만드는게 아니라 가능하면 

함수의 인자 값에 연산을 하여 if문을 간결하게 만든다. 

 

3.길을 2개 동시에 가게하려면 재귀문 2개를 연달아 쓰면 된다.

ex) 

solution(day + time[day], pTotal + price[day]);
solution(day + 1, pTotal);

 

내 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

class Consult{
	int Ti;
	int Pi;
	public Consult(int ti, int pi) {
		Ti = ti;
		Pi = pi;
	}
}

public class Main {

	public static int N; 
	public static int max; 
	public static Consult arr[];
	public static int select[];
	public static void backtrack(boolean End,int start) {
		if(End || start==N) { // 종결 
			int sum=0;
			for (int k = 0; k < N; k++) {
				if(select[k]==2) {
					sum+=arr[k].Pi;
				}
			}
			max=Math.max(max, sum);
			return;
		}
		for (int i = start; i < N; i++) { // 전체를 돌면 루프 밖으로 나가서 결과 값내기 
			
			if(i+arr[i].Ti-1 >=N) { //끝에 도달시 
				backtrack(true,0);
				
			}else {// 아직 남아있다. 
				
				select[i]=2;
				int j;
				for ( j= 1; j < arr[i].Ti; j++) {
					select[i+j]=1;
				}
				backtrack(false,i+j); // 할게 남아 있을때
				for (j = 0; j < arr[i].Ti; j++) {
					select[i+j]=0;
				}
			} // 끝에 도달시 
			
		}
		
		
	}
	public static void main(String[] args) throws IOException {
		BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer stkz;
		stkz= new StringTokenizer(br.readLine());
		N=Integer.parseInt(stkz.nextToken());
		arr =new Consult[N];
		select = new int[N];
		//입력 부 
		for (int i = 0; i < N; i++) {
			stkz= new StringTokenizer(br.readLine());
			int Ti=Integer.parseInt(stkz.nextToken());
			int Pi=Integer.parseInt(stkz.nextToken());
			Consult con = new Consult(Ti,Pi);
			arr[i]=con;
		}
		
		backtrack(false,0);
		System.out.println(max);
	}

}

 다른 코드 중 , Consultant 객체를 생성하지 않고 

time 과 price 각각 1차원 배열로 선언한 코드도 있었다. 

물론 나보다 성능이 더 좋았다. 

백준 아이디: chungdk1993 님 코드이다.

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static int n, answer;
    static int[] time, price;
    
    public static void main(String[] args) throws Exception {
	String[] cmd;
	n = Integer.parseInt(br.readLine());
	
	time = new int[n + 1];
	price = new int[n + 1];
	
	for(int index = 1; index <= n; index++) {
	    cmd = br.readLine().split(" ");
	    
	    time[index] = Integer.parseInt(cmd[0]);
	    price[index] = Integer.parseInt(cmd[1]);
	}
	
	solution(1, 0);
	
	System.out.println(answer);
    }

    private static void solution(int day, int pTotal) {
	if(day > n + 1) {
	    return;
	}
	
	if(day == n + 1) {
	    if(answer < pTotal) {
		answer = pTotal;
	    }
	    return;
	}
	
	solution(day + time[day], pTotal + price[day]);
	solution(day + 1, pTotal);
    }
}

 

입력 부분방법에 따라 시간이 다르게 나와 비교해봤다.

입력 부분 비교 

공통: 3개 모두 입력부에 BufferedReader (new InputStreamreader)를 썼다.

차이:

위에서 부터 

배열에 값할당 할때

1.  br.readLine과 split 만 씀 (72ms) -가장 빠르다

N=Integer.parseInt(br.readLine());
time =new int[N];
price = new int[N];
//입력 부 
for (int i = 0; i < N; i++) {
	String [] sb= br.readLine().split(" ");
	time[i]=Integer.parseInt(sb[0]);
	price[i]=Integer.parseInt(sb[1]);
}

 

2. StringTokenizer를 쓰면 조금 더 오래걸린다 (76ms) 

근데, nextToken쓰는게 편리할때가 있음!

StringTokenizer stkz;
stkz= new StringTokenizer(br.readLine());
N=Integer.parseInt(stkz.nextToken());
time =new int[N];
price = new int[N];
//입력 부 
for (int i = 0; i < N; i++) {
	time[i]=Integer.parseInt(stkz.nextToken());
	price[i]=Integer.parseInt(stkz.nextToken());
}

3. 2번 과 동일하게 StringTokenizer를 썼는데, 

클래스에다가 담아서 썼다 - 2번의 배열보다는 확실히 오래걸린다. ( 클래스 내부 -> 변수 까지 접근해야되서 )

class Consult{
	int Ti;
	int Pi;
	public Consult(int ti, int pi) {
		Ti = ti;
		Pi = pi;
	}
}

StringTokenizer stkz;
stkz= new StringTokenizer(br.readLine());
N=Integer.parseInt(stkz.nextToken());
arr =new Consult[N];
select = new int[N];
//입력 부 
for (int i = 0; i < N; i++) {
	stkz= new StringTokenizer(br.readLine());
	int Ti=Integer.parseInt(stkz.nextToken());
	int Pi=Integer.parseInt(stkz.nextToken());
	Consult con = new Consult(Ti,Pi);
	arr[i]=con;
}