개요
연구실에서 알고리즘 스터디를 해 보기로 했다.
스터디 명은 FDA인데, Fighting!! DMLab Algorithm이다. ㅋㅋㅋ
난이도는 solved.ac 기준 실실골골골플 정도로 하기로 했다.
풀이를 각자 적어 공유하는 방식으로 진행하기로 해서, 쓰는 김에 블로그에 적는다.
이번 주 문제는 내가 뽑았다.
A번: ATM
문제 요약
N명의 사람이 있고, 각자 ATM을 사용하는 데 걸리는 시간이 있다.
한 명씩만 쓰고 나머지는 대기해야 할 때,
대기 시간을 포함해 각 사람이 ATM 사용을 완료하기까지의 시간들의 총합을 구하는 문제다.
설명
사용 시간의 총합은 고정이니 대기 시간을 줄여야 한다.
그를 위해서는 사용 시간이 짧은 사람을 앞에 배치하면 된다.
정렬해서 계산하면 끝이다.
B번: 쿼드트리
문제 요약
0과 1로 이루어진 그리드를 쿼드트리 형태로 압축하는 문제다.
설명
쿼드트리는 트리이므로 재귀적으로 처리하면 된다.
재귀적으로 아래 과정을 수행한다.
- 내가 리프라면 해당 칸 값 반환
- 자식 노드가 모두 같은 꽉 찬 노드라면 압축해서 반환
- 아니라면 자식 노드 값 다 합치고 괄호로 감싸서 반환
구조체 같은 걸 만들어 처리하고 마지막에만 문자열을 뽑는게 효율적이겠지만 그냥 문자열 반환하는 재귀함수로 했다.
C번: 밤양갱
문제 요약
요약이 애매하므로 직접 확인하자.
설명
처음 몇 개를 직접 해 보면 규칙성을 찾을 수 있다.
첫 daldidalgo까지는 그냥 세 보면 8회
두 번째 daldidalgo부터는 복사하면 되므로 +1회
마지막 daldidan은 daldida까지 복사하고 n이므로 +2회다. 그럼 그 사이가 문제인데, N=4, N=8같은 경우는 기존걸 2배 한다고 생각하면 된다.
헷갈리는 부분이 $N=3$과 같은 경우인데, daldidalgo daldidalgo 상태에서는 daldidalgo daldida까지 복사를 해야 한다는 점이다.
그래서 $N=2$일 때 $11$, $N=3$일 때 $11$이다.
이는 깔끔한 거듭제곱이 가능해지는 $N=4$에서 $12$가 되면서 끝나고, $N=5$, $N=6$, $N=7$도 같은 이유로 $N=4$와 같은 값이 나오다가 $N=8$에서 끝난다.
따라서 $\log{N}$의 내림이라는 것을 직관적으로 알 수 있다.
이 것들을 고려해 계산해보면, 그냥 $\log{N} + 10$이 된다.
D번: 나이트의 이동
문제 요약
나이트가 특정 칸 $(x1,y1)$에서 다른 칸 $(x2,y2)$로 몇 번의 행마로 움직일 수 있는지 계산하는 문제다.
설명
단순 BFS로 풀 수 있다.
E번: 축구
문제 요약
18번의 시간 간격이 있고, 각 시간 간격마다 골을 넣을 확률이 주어진다.
골 스코어가 소수로 끝날 확률을 구하는 문제다.
설명
두 팀이 각각 확률을 가지고 있는건 별 의미 없고, 그냥 각 팀마다 확률을 구한 뒤 합해주면 된다. 따라서 한 팀 기준의 풀이를 생각하자.
문제의 정의를 그대로 수학적으로 나타내면 그게 풀이 끝인 재밌는 문제인데,
골을 넣을 확률을 $a$라고 할 때, 이산확률변수 $X$를 만들고 매 분마다 $ X = (1-a) \cdot X + a \cdot (X+1) $를 해 주면 끝이다. 말 그대로 $1-a$ 확률로 골을 못 넣고, $a$ 확률로 골을 넣어 1점이 추가되는 것이다.
이산확률변수라고 하면 당황스러울 수 있는데, (확률, 값)의 리스트라고 생각하면 쉽다. 실제로도 그렇게 구현하면 된다.
확률변수에 대한 곱셈이나 덧셈은 리스트 내의 모든 아이템에 대해 해 주면 된다.
예를 들어 X = [(1, 0)]에서 시작할 것이고 a=0.6이라면 1간격 뒤, X = [(0.6, 1), (0.4, 0)]이 될 것이다.
이 과정을 반복한 뒤, 값이 소수인 확률의 합을 구하면 된다.
F번: 너 봄에는 캡사이신이 맛있단다
문제 요약
수열이 주어졌을 때, 모든 조합의 최대-최소의 합 구하기.
설명
일단 어렵지 않게 $N^2$ 풀이를 떠올릴 수 있다.
최소와 최대만 중요하므로, 최소와 최대의 인덱스를 $i, j$라고 하면 해당 값들만 고정시킨 뒤 안의 모든 건 $2^{j-i-1}$개의 경우가 된다. 따라서 모든 i,j 쌍에 대해 $(A[j] - A[i]) \cdot 2^{j-i-1}$을 구하면 된다.
하지만 $N \leq 300,000$이므로 더 빠른 풀이가 필요하다.
위에서 구한 식은 $(i, j)$쌍 기준으로 생각한 것이다. 하지만 저 식이 쭉 나열된다고 쳤을 때, 특정 $A[i]$에 대해서만 모은다면 어떻게 될까?
$A[i]$는 $2^{i}-1$번 더해지고 $2^{N-i-1}-1$번 빼진다는 형태로 정리가 가능하다.
따라서 모든 $i$에 대해 $(2^{i}-2^{N-i-1}) \cdot A[i]$를 구해 합하면 된다.
재밌는 문제였다.
후기
ICPC가 끝난 뒤 목표를 잃기도 했고 많이 바쁘기도 해서 PS를 완전히 놓고 있었는데, 오랜만에 푸니 역시 재밌었다.
특히 E번과 F번은 수학적으로 깔끔하게 풀려서 기분이 좋았다.