ps:problems:boj:13018
특이한 수열
ps | |
---|---|
링크 | acmicpc.net/… |
출처 | BOJ |
문제 번호 | 13018 |
문제명 | 특이한 수열 |
레벨 | 골드 4 |
분류 |
애드혹 |
시간복잡도 | O(n) |
인풋사이즈 | n<=10^5 |
사용한 언어 | Python 3.13 |
제출기록 | 37928KB / 72ms |
최고기록 | 52ms |
해결날짜 | 2025/04/03 |
풀이
- n-k개의 수는 서로소가 되고, k개의 수는 서로소가 안되어야 한다.
- 차이가 1인 두 수는 서로소가 된다는 사실을 이용하면, 1≤i≤x-1인 i에 대해서 A[i]=i+1 로 정하는 방식으로, 모두 서로소가 되도록 만들수 있다. A[x]=1 로 두면, 1부터 x까지의 수를 사용해서 gcd(i, A[i]) > 1 을 만족하는 i가 한개도 없도록 만들 수 있다. x≤i≤n 까지의 i에 대해서는 A[i]=i가 되도록 하면, 거기에 포함되는 (n-x+1)개 수들은 모두 gcd(i, A[i]) = i > 1를 만족하게 된다.
- 그러므로 n-x+1 = k 가 되도록 x를 잡아서 저대로 만들어주면 끝. k=n 일때만 불가능으로 처리해주면 된다.
- 시간복잡도는 O(n)이다.
코드
"""Solution code for "BOJ 13018. 특이한 수열".
- Problem link: https://www.acmicpc.net/problem/13018
- Solution link: http://www.teferi.net/ps/problems/boj/13018
Tags: [ad hoc]
"""
def main():
n, k = [int(x) for x in input().split()]
if n == k:
print('Impossible')
return
answer = [*range(2, n - k + 1), 1, *range(n - k + 1, n + 1)]
print(*answer)
if __name__ == '__main__':
main()
ps/problems/boj/13018.txt · 마지막으로 수정됨: 2025/04/03 14:17 저자 teferi
토론