[BOJ 24548] 백준 24548번 - 도로 정보

		2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 풀이
A		[BOJ 24542] 튜터-튜티 관계의 수
C		[BOJ 24544] 카카오뷰 큐레이팅 효용성 분석
D		[BOJ 24545] Y
G		[BOJ 24548] 도로 정보
K		[BOJ 24552] 올바른 괄호
L		[BOJ 24553] 팰린드롬 게임

1. 문제

$24548$. 도로 정보 (2022 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2022 Winter) Open Contest G번)

백준 24548번 - 도로 정보 (https://www.acmicpc.net/problem/24548)

2. 풀이

$T, G, F, P$ 각각이 $3$의 배수 개수가 되어야 한다. 따라서 누적합을 구하고 이를 $3$으로 나눈 나머지가 어떠한 $i, j$ index에서 동일하면, $i+1\sim j$ 구간이 흥미로운 구간임을 알 수 있다.

$3$으로 나눈 나머지는 $0, 1, 2$만 존재하기 때문에 $dp[3][3][3][3]$으로 모든 데이터를 다룰 수 있다. $dp[a][b][c][d]$는 $t, g, f, p$의 개수가 각각 $a, b, c, d$(누적합을 $3$으로 나눈 값)인 index의 개수를 의미한다.

어떤 index $X$에서 $t, g, f, p$의 개수가 $a, b, c, d$라고 가정한다. 만약 이전의 index중에 index $Y$에서 $t, g, f, p$의 개수가 똑같이 $a, b, c, d$였다면, $Y+1\sim X$의 흥미로운 구간이 새롭게 형성된다.

따라서 index $X$에서 새롭게 형성되는 흥미로운 구간의 개수는 미리 저장해 놓았던 값인 $dp[a][b][c][d]$임을 알 수 있다.

3. 채점 결과

4. 회고

처음에 어렵게 돌아가는 식으로 접근하여 메모리와 시간이 상당히 소모되었다. 나중에 채점 현황에서 “gina(40245610)”님의 풀이를 보고 아이디어를 얻어 새롭게 작성하였다.

5. 코드