λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°
Algorithm

[λ°±μ€€] 1188번: μŒμ‹ν‰λ‘ κ°€(κ΅¬ν˜„, μ΅œλŒ€κ³΅μ•½μˆ˜)

by 주발2 2020. 4. 8.
λ°˜μ‘ν˜•

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

 

1188번: μŒμ‹ 평둠가

문제 μ„ μ˜μ΄μ˜ 직업은 μ†Œμ‹œμ§€ μš”λ¦¬μ‚¬μ΄λ‹€. μ†Œμ‹œμ§€λ₯Ό νŒ”κΈ° 전에 μŒμ‹ 평둠가 Mλͺ…을 λͺ¨μ•„μ„œ 맛을 ν…ŒμŠ€νŠΈν•΄λ³΄λ €κ³  ν•œλ‹€. μ„ μ˜μ΄λŠ” λ™μΌν•œ μ†Œμ‹œμ§€λ₯Ό 총 N개λ₯Ό μ€€λΉ„ν–ˆλ‹€. 이 μ†Œμ‹œμ§€λ₯Ό λͺ¨λ“  평둠가듀이 같은 양을 λ°›κ²Œ μ†Œμ‹œμ§€λ₯Ό 자λ₯΄λ €κ³  ν•œλ‹€. μ΄λ•Œ, μ†Œμ‹œμ§€λ₯Ό 자λ₯΄λŠ” 횟수λ₯Ό μ΅œμ†Œλ‘œ ν•˜λ €κ³  ν•œλ‹€. 예λ₯Ό λ“€μ–΄, μ†Œμ‹œμ§€κ°€ 2개, 평둠가가 6λͺ…μžˆλŠ” 경우λ₯Ό μƒκ°ν•΄λ³΄μž. μ΄λ•Œ, 각 μ†Œμ‹œμ§€λ₯Ό μ„Έ 쑰각으둜 λ§Œλ“  λ‹€μŒ, 각 ν‰λ‘ κ°€μ—κ²Œ ν•œ 쑰각씩 μ£Όλ©΄ λœλ‹€. 이 κ²½μš°μ— μ†Œμ‹œμ§€λŠ” 총 λ„€

www.acmicpc.net

μ½”λ“œ

import java.util.Scanner;

public class Main {
	public static int GCD(int a, int b) {
		if(b == 0)	return a;
		return GCD(b, a%b);
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		
		int N = scan.nextInt();
		int M = scan.nextInt();
		System.out.println(M - GCD(N, M));
		scan.close();
	}

}

풀이

이 λ¬Έμ œλŠ” ν’€μ΄λ§Œ μ•Œλ©΄ 정말 κ°„λ‹¨ν•˜μ§€λ§Œ,, κ·Έ 풀이λ₯Ό μƒκ°ν•΄λ‚΄λŠ”κ²Œ μ–΄λ ΅λ‹€.

μ²˜μŒμ— ν’€λ•ŒλŠ” Nκ³Ό M을 κΈ°μ€€μœΌλ‘œ N>M , N==M , N<M 으둜 λ‚˜λˆ„μ–΄μ„œ ν’€μ—ˆλŠ”λ°,

ν’€λ‹€λ³΄λ‹ˆκΉŒ 두 μˆ˜κ°€ μ„œλ‘œ λ°°μˆ˜μΈμ§€ μ•„λ‹Œμ§€μ— λŒ€ν•΄ 관련이 μžˆμ—ˆλ‹€.

λ˜ν•œ μ†Œμ‹œμ§€λ₯Ό μ΄μ–΄λΆ™μ΄λŠ” 방식에 λŒ€ν•΄ 생각을 λͺ»ν–ˆμ—ˆλ‹€.

κ°―μˆ˜μ™€ 상관없이 평둠가듀은 μ†Œμ‹œμ§€λ₯Ό N/M 개 만큼 κ°€μ Έκ°„λ‹€.

 

N = 3 , M = 5 ---> 1λͺ…λ‹Ή κ°€μ§€λŠ” μ†Œμ‹œμ§€μ˜ 수 = 3/5    --- ν•„μš”ν•œ 칼질 : 4회

N = 4 , M = 5 ---> 1λͺ…λ‹Ή κ°€μ§€λŠ” μ†Œμ‹œμ§€μ˜ 수 = 4/5    --- ν•„μš”ν•œ 칼질 : 4회

N = 6 , M = 3 ---> 1λͺ…λ‹Ή κ°€μ§€λŠ” μ†Œμ‹œμ§€μ˜ 수 = 6/3    --- ν•„μš”ν•œ 칼질 : 0회 

 

μ—¬κΈ°μ„œ, μ†Œμ‹œμ§€ N개λ₯Ό 이어뢙이면 μΉΌμ§ˆμ€ (M-1)번이 ν•„μš”ν•˜λ‹€.

ν•˜μ§€λ§Œ λ§ˆμ§€λ§‰κ³Ό 같이, N이 M의 배수일경우 μΉΌμ§ˆμ€ μ „ν˜€ ν•„μš”κ°€ μ—†λ‹€.

즉 μ΅œμ†Œν•œ M - GCD(N, M)번의 칼질이 ν•„μš”ν•˜λ‹€.

(μ΅œμ•…μ˜ 경우 GCD(N, M) = 1 ---> (M-1)번의 칼질)

 

λ°˜μ‘ν˜•

λŒ“κΈ€

πŸ”HALO