BOJ 15719 - 중복된 숫자

Joonas' Note

BOJ 15719 - 중복된 숫자 본문

알고리즘/문제 풀이

BOJ 15719 - 중복된 숫자

2018. 5. 18. 17:57 joonas 읽는데 1분
  • 문제
  • 풀이 1 (비트)
  • 코드
  • 풀이 2 (수학)
  • 코드

링크: https://www.acmicpc.net/problem/15719

문제

자료형의 비트를 이용하여 배열을 압축하여 사용하는 방법과, 수학으로 푸는 2가지 풀이를 소개하려 한다.

풀이 1 (비트)

표현할 정수의 범위는 [0, 10000000]이다. 그리고 필요한 정보는 각 숫자들이 사용되었는가/아닌가 이다.

사용되지 않았다면 0, 사용되었다면 1로 표현한다면 숫자 하나의 사용 여부를 하나의 비트로 관리할 수 있다.
즉, 32비트 정수 하나에 32개의 수의 상태를 담을 수 있다.

그럼 배열의 크기는 10 000 000/32=312 500만큼 필요하다. 코드는 훨씬 간단하다.

코드


풀이 2 (수학)

1부터 n1까지의 수가 골고루 등장한다. 등장한 모든 수의 합을 S, 한번 더 등장한 어떤 수를 m이라고 하자. 그럼 다음 식을 만족한다.
S=n(n1)2+m

n10,000,000 이므로 n(n1)도 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
Comments