[python] 백준 24228. 젓가락

문제

https://www.acmicpc.net/problem/24228

젓가락통에 N 종류의 젓가락이 종류별로 충분히 많이 들어있다. 당신은 이 젓가락통에서 무작위로 젓가락을 뽑아서 R개의 짝을 맞춰야 한다. 최악의 경우 몇 개의 젓가락을 뽑아야 하는가?

입력

두 개의 정수 N, R이 주어진다. (1≤N,R≤1018)$(1 ≤ N,R ≤ 10^{18})$ 

출력

최악의 경우 뽑아야 하는 젓가락의 개수를 출력한다.

 

---

풀이

이번 문제는 평소에 풀던 알고리즘들과는 다르게 수학적으로 접근해서 식을 구하고 그걸 그냥 코드에 넣어주기만 하면 되는 문제였다. 일단 먼저 코드 정답부터 올려놓겠다.

import sys
input = sys.stdin.readline

n, r = map(int, input().rstrip().split())
print((n+1)+(r-1)*2)

 

이렇게 짧은... 코드는 진짜 오랜만이지만.. 저 식을 생각해내기가 나한텐 쉽지 않았다.

이 코드에서 가장 중요한 부분은 당연하게도.

print((n+1)+(r-1)*2)

 

이 파트인데... 

일단 하나하나 뜯어서 봐보자면. 

1. n+1 

무조건적으로 한짝의 젓가락이 나올려면, 종류 중 하나는 무조건 들어와야한다.

 

2. r-1

위 1번 과정을 통해서 주어진 R개의 짝 중 하나는 이미 맞춘 상태가 되므로 r-1의 짝을 더 맞춰야하는 상태가 된다.

 

3. (r-1)*2

이때, r-1의 짝을 맞추는 과정을 구체적으로 생각을 해봐야하는데, 아까 1번 과정을 통해 제외된 젓가락과 동일한 것이 들어올 확률이 있기 때문에... 해당 종류와 동일한 젓가락을 넣는데 1회

그리고 아까 위 방식처럼 하나의 젓가락이 더 들어오는 과정으로 1회

해서 총 2번의 과정을 거치게 된다. 그리고 이 과정을 총 r-1 번 반복해야 최종적으로 최악의 경우 뽑아야 하는 젓가락의 개수를 구할 수 있다.

 

그렇게 해서!!!

나온 식이 바로

(n+1)+(r-1)*2 임을 알 수 있다.....

 

+) 시간복잡도를 구하지 않은 것 같아서 추가적으로 생각을 해보자면... 

입력부터 계산까지 다 한 번에 처리가 가능하므로 O(1)일 거라고 예상해본다. 

다른 방식은 시간초과가 난다.. 오직 이 식만을 구해야 풀 수 있는 문제 같다.