BOJ 문제풀이 W32

과외 마지막 주차 문제 풀이입니다

 

18886 new year and permutation

len : r - l이라고 할때,

$\sum\limits_{len}\left ( n-len+1 \right ) \times len! \times \left ( n-len+1 \right )!$, len = 1 to N

이를 구현해주면 문제를 해결 할 수 있습니다

다만 O(N) 안에 이를 구해야 함으로 팩토리얼 연산을 미리 전처리 해야합니다

또 이렇게 3가지를 곱할 때 m이 최대 10^9임으로 10^9를 3번 곱해주면 overflow가 발생합니다

3개를 동시에 곱해주지 말고 이 역시 나눠서 구해주면 해결 할 수 있습니다

 

11758 CCW

CCW 기본 문제입니다

신발끈 공식을 이용해 그대로 구현하면 됩니다

 

10840 구간 성분

N이 1500이라 N^2에 뒤에 로그하나 따라와도 문제를 해결 할 수 있습니다

흔히들 하는 라빈카프 해싱으로 문자열을 해싱해 줍니다

다만 순서는 상관 없이 같은 문자로 취급함으로 문자열에 포함된 각 알파벳의 갯수로 해싱해야합니다

 

이제 길이 len만큼 윈도우를 잡고,

문자열A를 밀어주면서 해시값을 set에 넣어줍니다

마찬가지로 문자열B에서 윈도우를 밀어주면서 이때 구한 해시값이 set에 있는지 확인해주면 됩니다

 

15573 채굴

강도 D에 대해 이분탐색을 해줍니다

이때 결정함수는 BFS를 통해 구한 광물의 수가 K이상이면 true입니다

다만 광물이 공기랑 닿은 부분만 채굴 가능해서 board에 -1로 테두리를 잘 채워주어야 합니다

 

이렇게 정말로 끝이 났네요

뭔가 아쉬우면서도 뿌듯하고 묘하네요☺️