본문 바로가기
2024-?학기 ???/Solving

SWEA 5215_햄버거 다이어트

by 껐다 켜보셨어요? 2024. 2. 29. 
import java.util.Scanner;
public class Solution {
	
	public static int loop;
	public static int[] eachT;
	public static int[] eachC;
	public static int totalC;
	public static int maxT;
	public static int size;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		loop = sc.nextInt();
		for(int i = 0; i<loop; i++) {
			size = sc.nextInt();
			totalC = sc.nextInt();
			eachT = new int[size];
			eachC = new int[size];
			
			for(int j = 0; j<size; j++) {
				eachT[j] = sc.nextInt();
				eachC[j] = sc.nextInt();
			}
			maxT = 0; // 초기화
			tasty(0, 0, 0);
			System.out.printf("#%d %d\n", i+1, maxT);
		} // for int i
	} // main
	
	public static void tasty(int idx, int sumC, int sumT) {
		
			if(sumC <= totalC) { // recursive
				if(sumT > maxT) {
					maxT = sumT;
				}
				if(idx+1 < size) {
					tasty(idx + 1, sumC, sumT); // 재료를 선택하지 않는 경우
					
					sumT += eachT[idx];
					sumC += eachC[idx];
					tasty(idx + 1, sumC, sumT); // 재료를 선택하는 경우
				}else if(idx + 1 == size) { // 마지막 케이스
					// 자체적으로 한 번 더 시행 (추가하는 경우만)
					sumT += eachT[idx];
					sumC += eachC[idx];
					
					if(sumC <= totalC) {
						if(sumT > maxT) {
							maxT = sumT;
						}
					}
					return; // 마지막 시행이므로 무조건 리턴한다
				} // else if (idx+1 == size)
				
			}else { // sumC > totalC 
				return;
			} // else
	} // static void tasty

}

 

남들 다 재귀 파라메터로 인덱스 하나 줄 때 나는 세 개 줌

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

}else if(idx + 1 == size) { // 마지막 케이스

// 자체적으로 한 번 더 시행 (추가하는 경우만)

이 부분 로직 구상에서 가장 헤맸다.

여기는 마지막 케이스이기 때문에 여기서 self 호출하면 무한반복됨

self에서 재귀 호출하는 부분 빼고 남은 로직을 넣어주면 된다.

여기에서 포인트는 재료를 추가하지 않는 경우를 고려하지 않는다는 것인데 

재귀 호출 로직을 보면 재료를 추가하지 않는 경우는 인덱스만 늘리고 그냥 이 케이스를 한 번 더 반복할 뿐이다. 

따라서 저 스코프에 들어온 순간이 이미 재료를 추가하지 않은 경우다. 

재귀는 오로지 다음 턴을 불러오는 경우에만 사용하는 것이고

마지막 케이스의 경우 다음 턴을 부를 필요가 없다.

따라서 sumC / sumT 값만 갱신해 주고 maxT 체크한 뒤 return하여 마무리한다.

그리고 .. .저 구문은 케이스 당 딱 한 번만 타게 된다. 

1 // TC IN

5 1000

100 200

300 500

250 300

500 1000

400 400

 

tasty(0, 0, 0) call ============1

not contains : 1 0 0 0

tasty(1, 0, 0) call ============2

not contains : 2 0 0 0

tasty(2, 0, 0) call ============3

not contains : 3 0 0 0

tasty(3, 0, 0) call ============4

not contains : 4 0 0 0

tasty(4, 0, 0) call ============5

new maxT : 4 400 400 0

contains : 4 1000 500 400

tasty(4, 1000, 500) call ============6

new maxT : 4 1000 500 400

func ends : 3

contains : 3 300 250 500

tasty(3, 300, 250) call ============7

not contains : 4 300 250 500

tasty(4, 300, 250) call ============8

new maxT : 4 700 650 500

contains : 4 1300 750 650

tasty(4, 1300, 750) call ============9

exceed totalC : ends.

func ends : 3

func ends : 2

contains : 2 500 300 650

tasty(2, 500, 300) call ============10

not contains : 3 500 300 650

tasty(3, 500, 300) call ============11

not contains : 4 500 300 650

tasty(4, 500, 300) call ============12

new maxT : 4 900 700 650

contains : 4 1500 800 700

tasty(4, 1500, 800) call ============13

exceed totalC : ends.

func ends : 3

contains : 3 800 550 700

tasty(3, 800, 550) call ============14

not contains : 4 800 550 700

tasty(4, 800, 550) call ============15

contains : 4 1800 1050 700

tasty(4, 1800, 1050) call ============16

exceed totalC : ends.

func ends : 3

func ends : 2

func ends : 1

contains : 1 200 100 700

tasty(1, 200, 100) call ============17

not contains : 2 200 100 700

tasty(2, 200, 100) call ============18

not contains : 3 200 100 700

tasty(3, 200, 100) call ============19

not contains : 4 200 100 700

tasty(4, 200, 100) call ============20

contains : 4 1200 600 700

tasty(4, 1200, 600) call ============21

exceed totalC : ends.

func ends : 3

contains : 3 500 350 700

tasty(3, 500, 350) call ============22

not contains : 4 500 350 700

tasty(4, 500, 350) call ============23

new maxT : 4 900 750 700

contains : 4 1500 850 750

tasty(4, 1500, 850) call ============24

exceed totalC : ends.

func ends : 3

func ends : 2

contains : 2 700 400 750

tasty(2, 700, 400) call ============25

not contains : 3 700 400 750

tasty(3, 700, 400) call ============26

not contains : 4 700 400 750

tasty(4, 700, 400) call ============27

contains : 4 1700 900 750

tasty(4, 1700, 900) call ============28

exceed totalC : ends.

func ends : 3

contains : 3 1000 650 750

tasty(3, 1000, 650) call ============29

not contains : 4 1000 650 750

tasty(4, 1000, 650) call ============30

contains : 4 2000 1150 750

tasty(4, 2000, 1150) call ============31

exceed totalC : ends.

func ends : 3

func ends : 2

func ends : 1

func ends : 0

#1 750

 

 

==

고치기 전 코드. 위 콘솔 프린트 구문 포함 

import java.util.Scanner;

 

public class Solution {

 

public static int loop;

public static int[] eachT;

public static int[] eachC;

public static int totalC;

public static int maxT;

public static int size;

 

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

 

loop = sc.nextInt();

for(int i = 0; i<loop; i++) {

size = sc.nextInt();

totalC = sc.nextInt();

eachT = new int[size];

eachC = new int[size];

 

for(int j = 0; j<size; j++) {

eachT[j] = sc.nextInt();

eachC[j] = sc.nextInt();

}

tasty(0, 0, 0);

System.out.printf("#%d %d\n", i+1, maxT);

}

}

 

public static void tasty(int idx, int sumC, int sumT) {

 

System.out.printf("tasty(%d, %d, %d) call ============\n", idx, sumC, sumT);

 

if(sumC <= totalC) { // recursive

if(sumT > maxT) {

System.out.printf("new maxT : %d %d %d %d\n", idx, sumC, sumT, maxT);

maxT = sumT;

}

 

if(idx+1 < size) {

System.out.printf("not contains : %d %d %d %d\n", idx + 1, sumC, sumT, maxT);

tasty(idx + 1, sumC, sumT);

 

sumT += eachT[idx];

sumC += eachC[idx];

 

System.out.printf("contains : %d %d %d %d\n", idx + 1, sumC, sumT, maxT);

tasty(idx + 1, sumC, sumT);

}

 

System.out.printf("func ends : %d\n", idx);

}else { // sumC > totalC

System.out.println("exceed totalC : ends.");

return;

}

 

 

}

 

}

1

5 1000

100 200

300 500

250 300

500 1000

400 400

tasty(0, 0, 0) call ============

not contains : 1 0 0 0

tasty(1, 0, 0) call ============

not contains : 2 0 0 0

tasty(2, 0, 0) call ============

not contains : 3 0 0 0

tasty(3, 0, 0) call ============

not contains : 4 0 0 0

tasty(4, 0, 0) call ============

// 이 부분을 지나면 더이상 TC에서 400, 400을 고려하지 않는다. else if(idx+1 == size) 컨디션이 없기 때문이다. 

func ends : 4

contains : 4 1000 500 0

tasty(4, 1000, 500) call ============

new maxT : 4 1000 500 0

func ends : 4

func ends : 3

contains : 3 300 250 500

tasty(3, 300, 250) call ============

not contains : 4 300 250 500

tasty(4, 300, 250) call ============

func ends : 4

contains : 4 1300 750 500

tasty(4, 1300, 750) call ============

exceed totalC : ends.

func ends : 3

func ends : 2

contains : 2 500 300 500

tasty(2, 500, 300) call ============

not contains : 3 500 300 500

tasty(3, 500, 300) call ============

not contains : 4 500 300 500

tasty(4, 500, 300) call ============

func ends : 4

contains : 4 1500 800 500

tasty(4, 1500, 800) call ============

exceed totalC : ends.

func ends : 3

contains : 3 800 550 500

tasty(3, 800, 550) call ============

new maxT : 3 800 550 500

not contains : 4 800 550 550

tasty(4, 800, 550) call ============

func ends : 4

contains : 4 1800 1050 550

tasty(4, 1800, 1050) call ============

exceed totalC : ends.

func ends : 3

func ends : 2

func ends : 1

contains : 1 200 100 550

tasty(1, 200, 100) call ============

not contains : 2 200 100 550

tasty(2, 200, 100) call ============

not contains : 3 200 100 550

tasty(3, 200, 100) call ============

not contains : 4 200 100 550

tasty(4, 200, 100) call ============

func ends : 4

contains : 4 1200 600 550

tasty(4, 1200, 600) call ============

exceed totalC : ends.

func ends : 3

contains : 3 500 350 550

tasty(3, 500, 350) call ============

not contains : 4 500 350 550

tasty(4, 500, 350) call ============

func ends : 4

contains : 4 1500 850 550

tasty(4, 1500, 850) call ============

exceed totalC : ends.

func ends : 3

func ends : 2

contains : 2 700 400 550

tasty(2, 700, 400) call ============

not contains : 3 700 400 550

tasty(3, 700, 400) call ============

not contains : 4 700 400 550

tasty(4, 700, 400) call ============

func ends : 4

contains : 4 1700 900 550

tasty(4, 1700, 900) call ============

exceed totalC : ends.

func ends : 3

contains : 3 1000 650 550

tasty(3, 1000, 650) call ============

new maxT : 3 1000 650 550

not contains : 4 1000 650 650

tasty(4, 1000, 650) call ============

func ends : 4

contains : 4 2000 1150 650

tasty(4, 2000, 1150) call ============

exceed totalC : ends.

func ends : 3

func ends : 2

func ends : 1

func ends : 0

#1 650

// else if(idx+1 == size)가 없기 때문에

// 다른 회차 시행에서 마지막 케이스인 400, 400을 고려하지 않는다.

// 따라서 100+250+300 =  650의 결과가 나온다. 

 

'2024-?학기 ??? > Solving' 카테고리의 다른 글

BOJ 17478_재귀함수가 뭔가요?  (0) 2024.03.03
SWEA 16268_풍선팡2  (0) 2024.02.29
SWEA 2817_부분 수열의 합  (1) 2024.02.27
SWEA 2817_부분 수열의 합(재귀)  (0) 2024.02.27
SWEA 1240_단순 2진 암호코드  (0) 2024.02.26

관련글

댓글

티스토리툴바