BOJ 15719 - 중복된 숫자
Joonas' Note
BOJ 15719 - 중복된 숫자 본문
- 문제
- 풀이 1 (비트)
- 코드
- 풀이 2 (수학)
- 코드
링크: https://www.acmicpc.net/problem/15719
문제
자료형의 비트를 이용하여 배열을 압축하여 사용하는 방법과, 수학으로 푸는 2가지 풀이를 소개하려 한다.
풀이 1 (비트)
표현할 정수의 범위는 [0, 10000000]이다. 그리고 필요한 정보는 각 숫자들이 사용되었는가/아닌가 이다.
사용되지 않았다면 0, 사용되었다면 1로 표현한다면 숫자 하나의 사용 여부를 하나의 비트로 관리할 수 있다.
즉, 32비트 정수 하나에 32개의 수의 상태를 담을 수 있다.
그럼 배열의 크기는 ⌈10 000 000/32⌉=312 500만큼 필요하다. 코드는 훨씬 간단하다.
코드
풀이 2 (수학)
1부터 n−1까지의 수가 골고루 등장한다. 등장한 모든 수의 합을 S, 한번 더 등장한 어떤 수를 m이라고 하자. 그럼 다음 식을 만족한다.
S=n(n−1)2+m
n≤10,000,000 이므로 n(n−1)도 long long형으로 커버가 가능하므로 구현이 쉽다.
코드
'알고리즘 > 문제 풀이' 카테고리의 다른 글
BOJ 1766 - 문제집 (2) | 2018.05.22 |
---|---|
BOJ 13701 - 중복 제거 (0) | 2018.05.18 |
BOJ 15683 - 감시 (2) | 2018.05.17 |
BOJ 1525 - 퍼즐 (0) | 2018.05.08 |
BOJ 2225 - 합분해 (0) | 2018.04.24 |