2024.01.15. ~ 2024.01.21.

최근에 블로그에 일지만 올리니까 블로그 자체가 내 PS 기록으로만 가득찰 것 같아 매일 마다 적어두고 일 주에 한 번씩 올리려고 한다.

사실 매일마다 올리기 귀찮아서;;

 

백준 10 문제.

 

1. BOJ 27903 인생 - Unrated

Golfscript로 풀었다.

핸들 때문에 printf, print, cout 등등이 다 막혀서 매우 막막했던 문제.

근데 핸들에 따라서 난이도가 천지차이가 나므로 이건 아무리 생각해도 Unrated 문제가 맞다.

(만약 백준 핸들이 aaaaaa 이런식이면 파이썬으로도 쉽게 풀 수 있다... print(chr(97)+...) 이런식으로)

 

2. BOJ 15912 우주선 만들기 - G3  [업다운 랜덤디펜스 성공! Solved - 20: 42]

DP + PQ / Tree Set로 푼 문제.

DP[i]를 i번째 부품까지 살 때에 최솟값, MAX_W[j...i] 및 MAX_E[j...i]를 각각 j ~ i 부품들 중에 최대 W 및 E값이라 하면 아래와 같은 식을 세울 수 있다.

DP[i] = min(DP[i], DP[j] + MAX_W[j+1...i] * MAX_E[j+1...i], MAX_W[1...i] * MAX_E[1...i]) (1 < j < i)
그래서 MAX_W[j+1...i] 및 MAX_E[j+1...i]를 구하기 위해서 multiset을 활용해 구했는데... 나중에 생각해보니 PQ도 굳이 필요가 없었다.

그래서 맞춘 후에 PQ / Tree Set 없이 다시 풀어보니 0ms 로 답이 잘 나왔다.

 

3. BOJ 2749 피보나치 수 3 - G2 [업다운 랜덤디펜스 성공! Solved - 05:37]

분할정복을 활용해서 행렬 제곱을 하는 문제.

A = [[1,1],[1,0]]라면 A^N한 결과 B에서 B[1][1]이 답이 된다.

너무 유명하고 이미 아는 유형이여서 쉽게 풀었다.

 

4. BOJ 19643 좀비 떼가 전역 때보다 먼저 오다니 - P3

백트래킹 + 휴리스틱 문제.

백트래킹 문제 같이 보이긴 했는데 이걸 나름 계속 커팅했어도 계속 TLE 나길래 DP인가 살짝 기웃거렸다.

그래도 DP로도 이거 못 풀 것 같아서 태그를 확인했는데... 휴리스택 태그 붙은 거 보고 뒷머리를 잡았다.

결국에 아래 조건들을 붙여서 커팅을 해서 풀었다.

• B1_power >= B2_power 라면 굳이 B2는 고려할 필요 없다.
• B3은 업데이트 범위가 O(L)이므로 현재 맨 앞에 있는 좀비를 꼭 죽여야 하는 상황인데 B3로 못 죽이면 볼 필요가 없다.

난 그저 그냥 BOJ 19644 푼게 기억나서 본건데... 왜 정답률이 10%에 머무르고 있는지 알 것 같다.

커팅 기술을 통해서 최적화하는건 나도 삼성 알고리즘 특강하면서 매우 흥미로운 주제라고는 생각하는데, 이 문제는 아에 이런식으로 커팅하는게 정해여서 난이도를 기여하지 않았다. 내가 제출한 풀이보다 더 빠른 풀이들이 존재하는 걸 보면 이게 정해는 아닌것 같은데... 에디토리얼이 인터넷에 뒤져도 안 나오니 원;;;

 

5. BOJ 1117 : 색칠 1 - G5

수학 문제.

f <= W-f 라는 가정하에서 설명해보도록 하겠다.

색칠이 끝나고 다 펴보면 f 기준으로 오른쪽은 접은 상태에서 색칠한 칸의 개수 * (c+1)개가 색칠되어 있을 것이다.

왼쪽은 색칠된 칸의 개수가 같거나 더 적을 수 있는데, 왼쪽과 맞닿은 칸들의 개수를 따로 계산해서 이에 c+1을 곱해주면 된다.

이제 이 둘을 합치면 총 색칠된 칸의 개수가 되니 답을 쉽게 구할 수 있다.

참고로 f > W-f 면 그냥 오른쪽과 왼쪽의 케이스가 서로 바뀐거라 그냥 f대신에 W-f를 기준으로 접어서 풀어도 된다.

G5 ~ G3 랜덤디펜스를 하려다가 찾은 문제. 시간은 제대로 재보지는 않았지만 한 10~20분 내로 푼 것 같다.

 

6. BOJ 14925 : 목장 건설하기 - G4

DP + Prefix Sum 문제.

행렬 내에서 제일 큰 정사각형 크기를 찾는 문제. (i,j)  좌표에 대해서 최대 크기가 S라면 (i-1,j), (i, j-1), (i-1,j-1) 에 대해서는 최대 크기가 S-1 이상이어야 한다. 따라서, dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])을 만족하면 된다.

웰노운 DP 문제로 2D Prefix Sum 기본 문제라 생각한다.

 

7. BOJ 1915 : 가장 큰 정사각형 - G4

 DP + Prefix Sum 문제.

한 변의 크기가 아니라 넓이를 출력하는 것 제외하고는 BOJ 14925랑 동일하다.

기여창에 같은 문제라길래 같이 풀었다.

 

[제 3회 보라매컵 예선 Open Contest] - 3 문제.

8 ~ 10. 이 문제들은 나중에 예선 오픈 콘테스트 후기 남기면서 다뤄볼 예정.

마지막 F번을 내가 퍼솔 먹어서 너무 행복했다 ㄹㅇㅋㅋ

마지막 F번 퍼솔 및 300점이라는 점수로 3등까지 달성한 나

 

이번주 일지는 여기서 끝.