골드 이상 풀이 정리 2주차

1. 숫자 연결하기 (BOJ 1323)

pigeonhole principle

 

언제 한번 순환소수 구할 때 나눗셈을 해본 적이 있다면 좋은 아이디어를 떠올릴 수 있다.

1. 수를 계속 추가하면서(순환소수라면 0이었고, 이 문제에서는 N이다.) K로 나눠서 나머지를 알아낸다. 그후 그 나머지+N(여기선 문자열 연산이라 생각)을 다시 합쳐서 K로 나눈다.

2. 계속 하다보면 언젠가 반복되었다.

즉, 예제를 생각해보면 2%9=2 -> 22%9 -> 42%9 -> 62%9 -> ... 이런 식으로 계속 연산해준다. K로 나눈 나머지는 반드시 0~K-1이므로 비둘기집 원리에 따라 최대 K번 안에 반복된다. 같은 나머지가 나왔는데도 나머지가 0으로 안 나온다면 영원히 못 나누므로 -1을 출력하고 아니면 횟수를 출력하면 된다. 같은 수가 나오는 지 판별은 간단하게 해시를 사용했다.

 

2. Division Expression (BOJ 3397)

greedy, euclidean

 

(1/2/(2/3)) 같은 겹괄호는 안되고, 괄호를 이용해서 주어진 식을 정수로 만들어야 한다.

일단 괄호를 어떻게든 씌워도 반드시 $x_1$은 분자고 $x_2$는 분모이다. 여기서 최대한 정수로 만들어줘야 하니 최대한 $x_i$들을 분자로 다 만들면 된다. 즉 $x_3$부터 $x_n$까지 전부 분모로 만들 수 있다. 즉 $x_1$/($x_2$/$x_3$/$x_4$/$x_5$/.../$x_n$)으로 괄호를 이용하면 $x_2$를 제외하고 모두 분자가 된다. 그러면 $x_1$, $x_3$, ... ,$x_n$의 곱이 $x_2$의 배수면 된다. 즉 저 둘의 최대공약수로 계속 나눠 $x_2$가 1이면 "YES", 아니면 "NO"를 출력하면 된다.

 

3. Look Up (BOJ 6105)

stack

 

배열을 차례대로 확인하면서 안에 있는 값이 현재의 값보다 작다면 계속 스택에서 빼주면서 빼주는 값들이 있던 인덱스를 확인하여 현재 인덱스를 저장하면 된다. 이미 이러한 monotone stack 문제는 잘 알려져 있다.

 

4. 핑거 스냅 (BOJ 17394)

bfs, sieve

 

현재 노드가 있다면 1/3, 1/2, +1, -1의 노드를 방문 체크하면서 bfs를 돌려주면 된다. 만약 현재 노드가 A 이상 B 이하면 그 값이 소수인지 확인하고 핑거 스냅의 최솟값을 갱신해준다.

 

5. 곱하기와 쿼리 (BOJ 28421)

number theory

 

1번 질의의 경우 $x$를 두 정수의 곱으로 만들 수 있는지에 대한 판별은 $x$를 소인수분해 하여 정수의 곱을 확인해주면 된다. 그 정수들이 배열에 있는지 확인하면 끝이다. 이는 후자에 얘기하는 어떤 정수가 수열에 몇 개인지 확인하는 배열을 만들면 된다. 2번 질의는 현재 배열에서 $i$번째 값이 무엇인지 확인해서 바꿔주기만 하면 된다. $A_i$가 최대 1만이고, $x$는 최대 1억이므로 크기가 1만개인 카운팅 할 수 있는 배열을 만들어서 계산해도 된다.

 

6. 팩토리얼 분수 방정식 (BOJ 13723)

number theory

 

$XY-N!(X+Y)=0$으로 먼저 바꾸면 뭔가 곱으로 나타낼 수 있을거 같다. $(X-N!)(Y-N!)=XY-N!(X+Y)+(N!{)}^2$이므로 $(X-N!)(Y-N!)=(N!{)}^2$이 되는데 $N!,X,Y>0$이므로 결국 $(N!{)}^2$의 (양의 정수 $X^{\prime }$, 양의 정수 $Y^{\prime }$)쌍의 개수를 찾으라는 것이다.

이는 약수의 개수와 동치다. $N!$의 약수 개수 찾는 법만 알면 쉽게 풀 수 있다.

$N!=p_1^{q_1}\times p_2^{q_2}$ × ... ($p_i$는 소수, $q_i\ge 0$)이면, $(N!{)}^2=p_1^{2q_1}\times p_2^{2q_2}$ × ...이므로 $(2q_1+1)\times (2q_2+1)$×...이 답이다.

$N$이 ${10}^4$라서 큰 값이 들어올 수 있으므로 파이썬을 사용하자.

 

7. 알렉산드리아의 디오판토스 (BOJ 7516)

number theory

 

위의 문제보다 더 쉬운 문제. $N^2$의 정수 곱의 쌍을 찾는 것이지만 대칭인 것(예시: {1, 5}, {5, 1})은 같은 것으로 취급 하기 때문에 결과값에 반으로 나누고 1을 더해주면 된다.

 

8. 짱해커 이동식 (BOJ 25603)

parametric search

 

현재 인덱스를 idx라고 하면 min(arr[idx:idx+k])을 찾고 이 값들 중에서 가장 큰 값이 답이다. 그리고 이 값이 있는 idx의 바로 다음부터 다시 k개의 구간을 idx+k가 n을 벗어나지 않을때 까지 반복해준다. 구간에서 최솟값을 찾는건 여러가지인데 생각이 안나서 그냥 세그로 O(logn)에 찾아줬다.

한편으로 파이썬에서 배열을 그대로 복사해서 min 값을 찾아주는게 세그보다 더 빠르다는 것을 찾아냈다. 데이터가 부족한거 같아서 데이터 추가 요청을 했다.