2024.04.29. ~ 2024.05.05.

백준 4 문제.

 

1. BOJ 1256 : 사전 - G2

DP + Combinatorics 문제.

 

가능한 모든 문자열의 개수는 N+M C M 이 된다. 그러면 현재까지 i개의 a와 j개의 z를 사용했다면 가능한 나머지 문자열들의 개수는 N+M-i-j C M-j가 된다. 이를 활용한다면 현재 자리에 a를 박았을 때 가능한 나머지 문자열들의 개수가 K 미만이라면 z를 꼭 사용하도록 구현해서 풀면 된다.

 

따라서, 모든 이항 계수를 DP 테이블로써 미리 계산을 해두고 현재까지 i개의 a와 j개의 z를 사용한 상태에서 a를 하나 더 박을 시 즉, N+M-i-j-1 C M-j가 K 미만이라면 z를 사용, 아니라면 a를 사용해서 정답을 채워 나가면 된다. 이렇게 말로만 표현하니깐 뭔가 애매한듯... 그래도 G2 DP를 25분만에 푼 건 오랜만인 것 같아 기분이 좋았다.

 

2. BOJ 19606 : Escape Room - G2

BFS 문제.

 

현재 있는 칸의 값이 y * x 꼴이 되는 칸들은 모두 갈 수 있다. 따라서 각 칸의 y * x를 계산해서 특정 칸에 도착했을 때 갈 수 있는 칸들을 미리 계산해둔다.

 

그러면 (1,1)부터 시작해서 이미 해당 칸의 값에 해당되는 좌표들을 탐색한 적이 있는지의 여부를 기준으로 탐색하면 된다. (같은 값을 이미 본 적이 있다면 중복해서 탐색하므로... 1차원 BFS를 이렇게 돌리면 된다.) 오랜만에 그래프 문제 풀고 싶어서 랜덤으로 뽑았는데 8분 컷났다. 아직 감이 안 죽어서 다행이다.

 

3. BOJ 1309 : 동물원 - S1

DP 문제.

 

i 번째 우리에 사자를 배치하는 방법은 1. 아무에도 배치 X, 2. 왼쪽에 배치, 3. 오른쪽에 배치 이렇게 세 가지가 있다.

그리고 이를 각각 dp[0][i], dp[1][i], dp[2][i]라고 한다면 아래와 같은 점화식을 생각할 수 있다.

 

- dp[0][i] = (i-1번째 우리에 사자가 어떻게 배치가 되든 상관이 없으므로) dp[0][i-1] + dp[1][i-1] + dp[2][i-1]

- dp[1][i] = (i-1번째 우리에 사자가 왼쪽에 배치가 되는 경우는 제외해야 함) dp[0][i-1] + dp[2][i-1]

- dp[2][i] = (dp[1][i]와 같은 원리) dp[0][i-1] + dp[1][i-1]

 

이렇게 점화식을 세우고 dp[0][N] + dp[1][N] + dp[2][N] 을 출력하면 된다.

 

4. BOJ 31797 : 아~파트 아파트 - S4

Math + Value Compression 문제.

 

상대적인 위치만 알면 되므로 2*M 배열로 상대적인 위치만 기록해둔다. 이때 값 압축을 하면 되는데, 위치 값이 1 ~ 10000 이므로 그냥 10000 크기의 배열에 기록하고 나중에 한 번 훑어봐서 상대적인 위치들을 파악하였다.

 

이후에는 몇 바퀴 도는 건지는 상관이 없으므로 (N-1) % (2*M)으로 위치를 바로 파악할 수 있다.

 

이번 주 일지는 여기서 끝.