Constructive 관찰(1)

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

1. 랜섬웨어와 비트코인(G4)

120까지 순회를 하는데 8개씩 끊어서 1부터20까지의 숫자를 저장할 수 있어야 함.

사이클 돌리는 것을 mod연산으로 구현할 수 있어야 함

arr[i%8] = i%20+1;

 

 

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

2. 돌의 정령 줄세우기

특정 숫자에 맞추려고 하기 보단 INF, 0로 무조건 조건을 만족하는 경우를 생각

1~N까지의 수를 뒤집고 시작

 

 

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

3. Key Knocking

key가 3의 배수로만 주어지는 점을 생각(왜 하필 3의 배수일까)

→ 3개씩 비트를 붙이면서 가중치가 최대가 되도록 계산

 

 

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

4. Irreducible Permutation

길이가 n인 배열이 순열이 되지 않기 위해서는 n번째 원소까지의 최댓값이 n보다 커야함.

순열은 길이가 n인 배열에 (1~n)까지의 숫자가 한번씩 모두 등장하는 것.

 

 

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

5. 특이한 수열

1 ≤ i ≤ n 인 i에 대해 gcd(i, A[i]) > 1 을 만족하는 i가 정확히 k개여야함

그러면 gcd(i,A[i])=1(서로소)을 만족하는 i는 n-k개

i=1일때는 무조건 gcd=1을 만족, 연속한 두 수는 gcd=1을 만족