[Algorithm] 백준 단계별로 풀어보기 - 단계 8. 규칙 찾기 (2)

BaekJoon Oline Judge - Step 8

1011. Fly me to the Alpha Centauri 

규칙 찾기 너무 어려웠던 문제 🤦🏻‍♀️

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		
		for(int i=0; i<T; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			
			int distance = y - x;
			int sqrt = (int) Math.sqrt(distance);
			int count = 0;
			
			distance -= (sqrt*sqrt);
			count = sqrt+(sqrt-1);
			
			int j = sqrt;
			if(distance > 0) {
				while(distance != 0) {
					distance -= j;
					if(distance >= 0) {
						count++;
					} else {
						distance += j;
						j--;
					}
				}
			}
			System.out.println(count);
		}
		scan.close();
	}
}

찾은 규칙은 distance -= (sqrt*sqrt)와 count = sqrt+(sqrt-1) 이다.

만약 2의 3승인 9라고 가정한다면,  1 2 3 2 1로(3: 최대 이동 거리) 총 합이 9가 되므로 남은 distance는 0이 될 것이고 count는 3+2를 한 5가 된다.

2의 4승인 16은 1 2 3 4 3 2 1로(4: 최대 이동 거리) 총 합이 16이므로 남은 distance는 0이 될 것이고, count는 4+3인 7이 된다.

 

따라서 최대로 이동할 수 있는 거리는 루트를 씌워 구해주면 되고, 소숫점이 발생한다면 버리면 된다.

 

예외는 2의 n승으로 나타낼 수 없는 수인데, 10을 예로 든다면 √(10)은 3.xxxx 이므로 소숫점을 뗀다면 3이 최대로 이동할 수 있는 거리이다. 1+2+3+2+1=9이므로 거리 1이 남게 된다. (if distance > 0)

이 경우 최대로 이동할 수 있는 거리인 sqrt부터 하나씩 감소시키면서 넣을 수 있는 수를 판단해준다. 3과 2를 넣으면 distance가 음수가 되므로 1이 들어가게 된다.

1-1=0으로 distance가 0이 되면 반복문을 빠져나와 count를 출력시킨다.

 

조금 큰 수인 9800을 예로 든다면, 남는 수는 196, √(9800)은 98.xxx이다.

들어갈 수 있는 가장 큰 수인 98을 196에서 빼준다. 98이 남는다. 다시 98을 빼준다. 0이 되므로 반복문을 빠져나온다.

 

 

2775. 부녀회장이 될테야

1	...	...	...	...
1	...	...	...	...
1	4	10	20	35
1	3	6	10	15
1	2	3	4	5

위와 같으므로 k층에 n호에 있는 사람의 수를 구하고 싶으면 (k층에 n-1호) + (k-1층에 n호)를 구하면 된다.

만약 4층에 3호라고 한다면 (4층에 2호) + (3층에 3호)

(4층에 2호)는 4층에 1호 + 3층에 2호, (3층에 3호)는 3층에 2호 + 2층에 3호 .....[계속 반복]

따라서 재귀함수를 이용하여 풀었다.

 

재귀함수를 빠져나오는 조건문이 필요한데, 위 표를 보면 k(층수)가 0일때는 n(호수)을 리턴하고 n(호수)가 1이 된다면 1을 리턴하는 것을 알 수 있다.

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		
		for(int i=0; i<T; i++) {
			int k = scan.nextInt();
			int n = scan.nextInt();
			
			int result = recursion(k, n);
			
			System.out.println(result);
		}
		scan.close();
	}
	
	public static int recursion(int k, int n) {
		if(k==0)
			return n;
		if(n<=1)
			return 1;
		 else
			 return recursion(k, n-1) + recursion(k-1, n);
	}
}

 

 

1475. 방번호

9, 6 갯수에 소수점 올림을 해주지 않아서 실패 카운트가 쌓였던 문제...!

969처럼 9, 6갯수가 홀수일 때 세트 갯수가 2개가 되어야하는데 소수점 올림을 해주지 않으면 1개로 카운트되니 주의

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		String N = scan.nextLine();
		scan.close();
		
		//문자열 길이
		int nLen = N.length();
		int[] setArr = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
		int res=0;
		
		//charAt index는 0부터 시작
		for(int i=0; i<nLen; i++) {
			int num = N.charAt(i) - 48;
			
			if(num==6 || num==9) {
				res++;
			}
			setArr[num]++;
		}
		
		if(res > 1) {
			res = (int) Math.ceil((double)res/2);
			setArr[6] = setArr[9] = res;
		}
		
		//최대값 출력
		Arrays.sort(setArr);
		System.out.println(setArr[setArr.length-1]);
	}
}

0~9까지의 배열을 선언하고, 방 번호를 문자열로 입력받아서 문자열 길이만큼 반복한다.

(문자 - 48)을 해서 해당 숫자를 만들어준다. 그 숫자를 인덱스로 사용하여 숫자가 몇번 사용되었는지를 센다.

만약 1211 이라고 하면, 1은 3번, 2는 1번 사용되었다. 1의 갯수인 3이 배열의 최대값이므로 3이 사용한 세트의 갯수가 된다.

 

여기서 다른 조건이 하나 더 붙는데, 6과 9를 같은 숫자로 보아야한다.

int res = 6과 9의 갯수

따라서 정수 변수를 하나 선언(res)해서 숫자가 6, 9일때만 ++해주고, 반복문을 다 돌고난 뒤 res가 1보다 크다면 나누기 2를하여 arr[6], arr[9]에 넣어준다.

9999라면 res는 총 4개인데, 6과 9를 같은 수로 보기 때문에 99/99 총 2개가 사용되기 때문이다.

 

 

6064. 카잉 달력

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int T = scan.nextInt();
		
		for(int i=0; i<T; i++) {
			int M = scan.nextInt();
			int N = scan.nextInt();
			int x = scan.nextInt();
			int y = scan.nextInt();
			
			int lcm = lcm(M, N);
			
			int xp=0, yp=0, cnt=-1;
			//최소공배수보다 작을 때
			for(int k=1; k<=lcm; k++) {
				if(xp < M) xp++;
				else xp=1;

				if(yp < N) yp++;
				else yp=1;

				if(xp==x && yp==y) {
					cnt = k;
					break;
				} else
					cnt = -1;
			}
			
			System.out.println(cnt);
		}
		scan.close();
	}
	
	public static int lcm(int M, int N) {
		int lcm = 0;
		
		for(int j=1; j<=M*N; j++) {
			if(M%N == 0) {
				lcm = Math.max(M, N); break;
			} else if(j%M == 0 && j%N == 0) {
				lcm = j; break;
			}
		}
		
		return lcm;
	}
}

M, N 최소공배수만큼 반복 돌렸더니 시간초과...(!) 나중에 다시 풀어봐야겠다