/ BOJ

BOJ_3060_욕심쟁이돼지_JAVA

문제 : 욕심쟁이 돼지

링크 : BOJ_3060_욕심쟁이돼지

접근 방식

원탁에 6명이 앉아있고, 각자 인접한 돼지와 맞은편의 돼지가 먹은 식량만큼 자신의 값에 더해줘야한다. 원탁을 기반으로 하기 때문에 배열의 참조를 원형처럼 접근해야한다. 이는 나머지연산으로 간단하게 할 수 있다.

조건에서 6마리로 정해져 있기 떄문에 6으로 나머지연산을 시켜주면서 index에 적절한 값을 더해주면된다.

나머지연산을 쓰지 않으려면 직접 어떻게 되는지 다 체크해서 모든 경우의 수를 코딩 할 수도 있다.

또 하나의 방법으로, 수학적으로 풀 수도 있다. 이번 문제의 경우에, 매 날짜마다 돼지들이 원하는 사료의 양은 4배씩 증가한다.

풀이 방법

  1. 배열에 첫 날 돼지들이 먹고 싶어하는 사료의 양을 저장한다.

  2. 맨 처음, 배열의 값을 다 더해서 sum변수에 저장한다. sum이 N보다 크다면 먹일 수 없다는 의미이므로 1을 출력하고 다음 테스트 케이스로 넘어간다.

  3. sum이 N보다 작다면, 날짜 반복으로 넘어간다. 카운트를 1 증가시키고, sum을 4배 증가시켜준다. 만약 증가시킨 sum값이 N보다 작다면 위 내용을 반복하고, N보다 크다면 반복을 종료한다.

  4. 반복이종료된 후 카운트 값을 출력하고, 다음 테스트케이스로 넘어간다.

  5. 모든 테스트 케이스가 테스트되었다면 프로그램을 종료한다.

소스 코드


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

public class BOJ_3060_욕심쟁이돼지 {

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		int T = Integer.parseInt(in.readLine());

		for(int tc = 0; tc<T;tc++) {

			long N = Integer.parseInt(in.readLine());


			long arr[] = new long[6];

			StringTokenizer st = new StringTokenizer(in.readLine()," ");
			for(int i=0;i<6;i++) {
				arr[i] = Integer.parseInt(st.nextToken());
			}
			long sum = 0;
			int cnt = 1;
			for(int i=0;i<6;i++) {
				sum = sum + arr[i];
			}

			if(sum > N) {
				System.out.println(cnt);
				continue;
			}
			while(true) {
				cnt++;
				sum = sum*4;
//				for(int i=0;i<6;i++) {
//					arr[i] = arr[i] + arr[(i+3)%6] + arr[(i+5)%6] + arr[(i+1)%6];
//					sum += arr[i];
//				}
				if(sum > N) {
					break;
				}


			}

			System.out.println(cnt);

		}


	}

}