https://www.acmicpc.net/problem/31229
31229번: 또 수열 문제야
다음 조건을 만족하는 길이 $N$의 수열 $A=\left\{A_{1},A_{2},\dots,A_{N}\right\}$를 출력하시오. $1\leq i<j \leq N$을 만족하는 모든 정수 $i$와 $j$에 대해서 다음 조건을 만족한다. $A_{i}\neq A_{j}$이고 수열 $A$의
www.acmicpc.net
24/01/15
젠장, 또 수열 문제야. 이 문제만 풀고 자려고 했는데, 수열 문제를 보고야 말았어. 이제 나는 풀어야만 해... 풀면 잠이 확 깨버릴 걸 알면서도, 나는 풀어. 그것이 수열 문제를 목도한 자의 사명이다.
문제 접근 방식:
간단한 아이디어가 있으면 쉽게 해결할 수 있다.
수열은 두 가지 조건을 만족시켜야 한다.
첫 번째로, 수열의 모든 원소는 달라야 한다.
두 번째로, 임의의 두 원소를 더한 값은 두 원소를 곱한 값의 약수가 되어선 안된다.
두 번째 조건을 만족시키는 것이 문제의 핵심이다.
강력한 스포일러가 될 수 있으니 충분히 생각을 하고 더 보기 버튼을 누르자.
홀짝을 생각해 보자. 우리는 (홀수)$\times$(홀수) = (홀수)이고, (홀수)$+$(홀수) = (짝수)라는 사실을 알고 있다.
그리고, 짝수는 절대 홀수의 약수가 되지 못한다.
따라서 그냥 홀수 수열을 출력하면 된다.
예제 출력을 보고 소수와 관련되게 답을 낸 사람도 있는 것 같은데, 그냥 홀짝성이 이용된다는 사실만 파악하면 쉽게 풀 수 있는 문제이다.
아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.
for i in range(int(input())):
print(2*i+1, end = ' ')'알고리즘 > 백준 문제 풀이' 카테고리의 다른 글
| [Python] 2084번 차수열 (0) | 2024.01.23 |
|---|---|
| [Python] 1038번 감소하는 수 (0) | 2024.01.23 |
| [Python] 4659번 비밀번호 발음하기 (0) | 2024.01.21 |
| [Python] 14395번 4연산 (0) | 2024.01.21 |
| [Python] 31218번 자료 구조의 왕 (0) | 2024.01.20 |