5/25~5/28 PS

주식회사 승범이네를 제외한 7문제.

그냥 6문제정도 쌓일 때마다 글을 올려야겠다. 귀찮아질 것 같아서...

 

 

BOJ 16679 - Back to the Bones (P5)

전처리 dp 문제이다. $dp[i][k]=$(i번째에서 주사위들의 눈의 합이 k가 나오는 경우의 수)라고 정의해보자. 주사위 $x$개를 다시 굴린다고 하면 눈이 가장 작게 나온 것들을 굴리는 것이 무조건 이득이다. 즉, y=(얻어야 하는 수)로 정의하면, $dp[x][y]$를 활용해 주사위를 몇 개 굴리는 것이 최적인지를 찾아내면 된다. 따라서 각 쿼리마다 $O(N^2)$에 해결할 수 있고, 전체 시간복잡도는 $O(N^3)$이다.

 

BOJ 12844 - XOR (P3)

레이지 세그 활용문제이다. 홀수/짝수를 나누어서 lazy propagation을 잘 짜주면 된다. 재귀적으로 함수를 짜면 파이썬으로 풀 수 없다;;

 

BOJ 12986 - 화려한 마을 2 (P2)

mo's 활용문제이다. 어떤 색의 개수를 세는 cnt 배열을 만들고, cnt의 개수를 세는 cntCnt 배열을 만들면 된다. (배열이 정렬된 배열이라는 점을 활용하여 세그트리로도 풀 수 있다. 나는 까먹었던 모-쓰의 기억을 다시 되살리기 위해 모--쓰로 풀었다.)

 

BOJ 6515 - Frequent values (P1)

위 문제와 같은 문제이다. (배열이 정렬되어있지 않으므로, 12986번에서 사용한 세그트리 풀이는 불가능하다.)

 

BOJ 12999 - 화려한 마을 3 (P1)

역시 같은 문제이다. (배열이 정렬되어있지 않으므로, 세그트리 풀이는 역시 불가능하다.)

 

BOJ 8146 - Tetris Attack (D4)

$A,B,C,D,A,...$이 있을 때, $A,A,B,C,D,...$로 밀어도 상관이 없다는 점을 이용하면 된다. 다르게 말하면, 앞에서부터 볼 때 겹치는 수를 바로바로 합쳐도 상관이 없다는 것이다. 스택을 사용하여 $O(N)$에 쉽게 구현 가능하다.

 

BOJ 17407 - 괄호 문자열과 쿼리 (P2)

채점 현황을 조용히 지켜보다가, dong_gas님(블루 축하드립니다!)께서 푸신 문제를 나도 풀어보았다.

 

누적합 배열 $P$에서, $P[N]==0$이고 $min(P)==0$이면 올바른 괄호 문자열임을 이용하면 되는 문제이다. 최솟값 레이지 세그를 짜면 된다. 20052번보다 난이도가 약간 올라간 문제이므로 (풀이) 난이도는 P3이 맞아보인다.

 

지능이 오르는 기분이 들지 않는다. AC Rating만 오른 듯...