프로그래머스 숫자 카드 나누기

문제

https://school.programmers.co.kr/learn/courses/30/lessons/135807

프로그래머스

 

풀이

"한 사람이 가진 카드뭉치들의 수들을 모두 나눌 수 있는 수"

의미는 공약수이다. (공약수의 정의)

어떤 공약수는 최대공약수의 약수이다.

따라서 카드뭉치마다 gcd(최대공약수)를 구해줘야 다음으로 진행할 수 있다.

 

"어떤 수의 대해 한 사람이 가진 카드뭉치의 수는 하나라도 나누어지면 안된다."

한 카드뭉치의 gcd를 구한뒤 다른카드뭉치의 수가 하나라도 gcd로 나누어지면 방법이 없어진다.

gcd로 나누어진 단 것은 다른 공약수(gcd의 약수)한테도 나누어지기 때문이다.

 

풀이를 정리하자면

1. 각 배열마다 gcd를 구한다.

2. 각 gcd에 대해 다른 배열이 gcd로 나누어지는지 확인한다.

3. 나누어지면 해당 케이스는 0으로 처리

4. 두 케이스의 최댓값 출력