풀수 있었던 문제
A
시도한 문제
A, B
A번부터 J번까지 문제를 읽어본 결과 수열과 조합론이 주된 풀이 방식인 것 같았다.
역량이 부족한 건지 B번에서 막혔다. (다른 문제들은 풀이가 감도 안왔음.)
풀어본 것들 정리나 해야겠다...
A : K 정렬
(i+K) mod N 이므로, 처음에는 N%K가 0일 경우에만 생각을 했다.
N%K가 0일 경우 K가 N의 약수이므로 교체할 수 있는 위치가 제한된다. 따라서 i%K와 A[i]%K가 다르다면 교체할 수 없는 위치에 존재하므로 NO를 출력할 것이다.
그런데 이 경우 N이 20, K가 6일 경우 i가 0일때, 교체할 수 인덱스는 0, 2, 4, 6... 인데 K가 6이기 때문에 교체할 수 있는 위치가 달라지게 된다. 따라서 해당 반례에 의해 WA를 받았다.
반례에 맞추기 위해 입력을 확인하던 중 N = 20, K = 8 일때 교체 가능한 위치가 i=0일 때 기준 0 4 8 12 16 이었다.
왜 그런지 확인한 결과 N과 N-K의 gcd 값이 교체 가능한 간격이었다. (아마 N과 K의 gcd를 이용해도 가능할 듯.)
gcd 값이 1일 경우 모두 교체 가능하고, 이외의 경우 gcd 값을 교체 가능한 간격으로 이용하여 나머지 연산을 하고 i에도 동일하게 gcd 값을 나머지 연산할 시 다르다면 NO를 출력한다.
B : 또또 수열 문제야
수열을 예상하는 문제
임의의 수열에 대해, 수열A의 원소 개수 N개와 A[i]와 A[j]를 곱한 집합을 제시해준다. 이때 i, j는 1~N 사이의 임의 수이다.
이때 수열을 구성하는 문제인데, 골드 문제정도는 될 것 같은데 이걸 어떻게 구성해야할 지 감이 안온다.
미리 제곱수들을 N의 범위인 1001까지 구하긴 했는데 입력으로 오는 제곱수가 사실 i==j가 아닌 경우 어떻게 처리할 지 생각만 한 것 같다.
원소 개수 N개에 대해 [i**2-1]에 위치한 원소가 제곱수일 것이다... 라고 예측했었는데
a b c d 와 같이 수열이 구성되있을 경우
a*c <= b 인 경우도 있었다.
대회 풀이가 나올 때까지 기다리거나... 다른 사람이랑 같이 풀거나 질문을 해야 할 듯...
