[BOJ] 20952 게임 개발자 승희_binary search

가장 긴 증가하는 부분 수열2

문제

길이가 N인 수열 A
길이가 M인 수열 B

수열 A의 모든 원소에 B의 원소를 순차적으로 더 한 값중 7의 배수는 제거한다. 만약 수열 A의 모든 원소가 지워진다면 해당 연사는 수행하지 않는다. (최종 답은 10^9+7의 나머지를 출력해야한다)

제약 사항

해결 방법

수열 A, B를 전체 탐색하여 구현하였는데, 바로 시간초과가 났다. 현재 O(N*M)으로 연산되어 최대 10,000,000,000번의 연산이 되는데, 1초라는 제한시간은 훨씬 넘겨 버린다.

문제를 풀기 위해서는 O(N) 정도로 숫자를 줄여야한다.

연산 수를 줄이기 위해 나머지에 대한 성질을 이용했다.

c에 대한 나머지를 구할때, A,B 합한 후 구한 나머지와 각각의 나머지를 구한 값을 합한 값의 나머지는 같은 값을 갖는다.

(A+B)%c = (A%c+B%c)%c

나머지 연산의 분배 법칙을 이용하면, 수열 A를 획기적으로 줄일 수 있다. 문제 상황에서 A의 원소별로 동일한 값을 더하게 되고, 7로 나눈 나머지가 중요하다.

7, 14, 21, 28 는 결국 동일한 값을 갖게되고, 8, 15, 22 .. 동일한 값을 갖게 된다.

결국 A의 값들을 7로 나눈 값으로 변경하면, 총 7가지 값으로 반복된다. 수열 A의 원소를 7로 나눈 나머지를 구해 DP를 만들어 연산 해보려고 한다.

A=[1,8,4,3,6,9,2]
B=[1,2,3]

단계 별로 확인

수열 A 원소를 7로 나눈 나머지를 구함

A = [1,8,4,3,6,9,2] → A%7 = [1,1,4,3,6,2,2]
dp에 수열 A의 원소를 입력 해줌
```
 dp = [0]*7
 for i in A: 
     dp[i%7]=1
```
result : dp = [0,1,1,1,1,0,1]
수열 A에 수열 B의 원소 b1(1)을 더한 후 7로 나눠줌

A = [1,1,4,3,6,2,2]
→ +b1 = [2,2,5,4,7,3,3]
→ %7 = [2,2,5,4,0,3,3] # 나눠 떨어지는 원소 제거
수열 A에 수열 B의 원소 b2(2)을 더한 후 7로 나눠줌

A = [2,2,5,4,3,3]
→ +b2 = [4,4,7,6,5,5]
→ %7 = [4,4,0,6,5,5] # 나눠 떨어지는 원소 제거
수열 A에 수열 B의 원소 b3(3)을 더한 후 7로 나눠줌

A = [4,4,6,5,5]
→ +b3 = [7,7,9,8,8]
→ %7 = [0,0,2,1,1] # 나눠 떨어지는 원소 제거
연산한 수열 A = [2,1,1]
DP로 저장

dp=[0,1,1,0,0,0,0]
최종 결과 출력

수열 A에 B를 더한 값을 7로 나눈값이 1,2인 값을 뽑아냄
```
 a=[]
 for i in A:
     if dp[i%7] ==1:
         a+=[str((i+temp)%e)]
```
result : [9,15,8]

풀이

```python import sys input = sys.stdin.readline

e=1000000007 M,N = map(int,input().split()) A=list(map(int, input().split())) B=list(map(int, input().split()))

dp = [0]*7 for i in A: dp[i%7]=1 temp=0

for b in B: temp += b l = [1 if (i+temp)%7 !=0 and dp[i]==1 else 0 for i in range(7)] if sum(l)!=0: dp=l else : temp-=b

a=[] for i in A: if dp[i%7] ==1: a+=[str((i+temp)%e)] print(len(a)) print(‘ ‘.join(a))

result : 

![image](https://user-images.githubusercontent.com/77658029/124957354-f313ca80-e053-11eb-9b6d-2ff8181cfe22.png)

<br><br>

💡 수정 필요한 내용은 댓글이나 메일로 알려주시면 감사하겠습니다!💡 ```