8/23 ~ 8/28 PS

21, 22일은 여행 이슈

 

 

BOJ 25488 - 토큰 (P4)

scc에 속하는 토큰의 개수가 같은 채로 유지되어야 문제의 조건을 만족한다.

 

BOJ 23268 - Deceptive Directions (G2)

일단 bfs로 가능한 보물의 위치는 주어진 문자열을 통해서 대충 구해놓을 수 있다. 그러나, 경로는 무조건 최단경로여야 하므로 각 셀의 거리를 전처리하면 된다.

 

BOJ 17625 - 고압선 (D2)

 점 a, b, c에서 선분 ab와 점 c의 거리, 또는 어떤 두 점 사이의 거리 중 최대/2를 구해야 하는데, 어떤 두 점을 잇는 선분에서, 이와 수직인 선분을 지나는 다른 점은 존재해서는 안 된다. 이는 한 점을 90도를 돌리면 된다.

 이거를 불도저로 구하면 끝이다.

 

BOJ 16496 - 큰 수 만들기 (P5)

 a+b와 b+a를 비교하며 정렬하기

 

BOJ 23759 - 비슷한 문자열 (G2)

dp[n] = n번째 문자열을 반드시 포함할 때, 최대 길이 로 정의하고,

dpp[c][k] = 알파벳이 c이고 문자열 내 인덱스가 k일 때 가장 마지막 위치라고 정의하면 쉽게 풀린다.

 

BOJ 2336 - 굉장한 학생 (P2)

놀라운 문제였다. 1번째 기준으로 정렬하고, 2번째 등수에 3번쨰 등수를 집어넣으면 된다. 최솟값 세그로 풀린다.

 

BOJ 19455 - Bitwise Queries (R5)

세그비츠 문제다. 구간의 최솟값, 켜진 비트, 꺼진 비트들을 관리해주면 된다.