[2022 KAKAO Blind Recruitment] Q6. 파괴되지 않은 건물 (C++, Python, Java)

문제 링크

https://programmers.co.kr/learn/courses/30/lessons/92344

 

예상 난이도

G3

 

알고리즘 분류

DP

 

풀이

BOJ 11660번과 같은 문제를 풀어본 경험을 통해 이 문제를 보고 DP를 떠올릴 수 있어야 했습니다. 문제를 보고 DP를 떠올리지 못한 상태에서 문제의 풀이를 스스로 착안해내는건 거의 불가능했다고 보입니다.

 

2021 카카오 블라인드 광고 삽입 문제의 Prefix Sum에서 소개해드린 아이디어처럼 각 스킬을 처리할 때 스킬이 적용되는 모든 칸의 값을 변경하는 대신에 변화량만 기록을 하고 싶습니다. 그림에 있는 것 처럼 변화량 테이블의 (3, 4)가 1이라는 의미는 (3, 4)의 오른쪽 혹은 아래에 있는 12칸의 값이 전부 1 더해져야 한다는 의미입니다. 

 

이렇게 변화량 테이블을 정의했을 때 우리는 변화량 테이블을 이용해 각 스킬을 단 4개의 값만 변경하는 방식으로 저장할 수 있습니다.

 

그리고 변화량 테이블의 각 값은 자신의 오른쪽과 아래에 있는 모든 칸에 전파가 되어야 하니 오른쪽 방향으로 누적합을 한 번 돌리고 다음으로 아래쪽 방향으로 누적합을 한 번 돌리면 깔끔하게 해결됩니다.

 

안물안궁일수도 있지만 사실 저도 이러한 형태의 누적합 풀이를 이전에 접해본 적이 없었습니다. 그러면 저는 당시 문제를 어떻게 풀었냐면, 사실 배우신 분들이라면 2차원 세그먼트 트리나 pst등 괴상한 자료구조들이 머릿속에 맴돌았을 수 있겠지만 저는 분명 dp를 이용한 간단한 풀이가 있을거라는 확신을 가지고 구글에 2d update query constant라고 검색을 해서 이 글을 찾았습니다. 사실 여기처럼 검색이 허용되는 코딩테스트라고 하더라도 ps 공부 경험이 많지 않다면 문제를 보고 어떤 키워드로 검색을 해야 하는지 자체를 감을 못잡을 가능성이 큽니다. 그래서 여러분들이 검색으로 뭔가 유용한걸 건지긴 힘들겠지만 그래도 앞으로 여러분들도 블로그든 아니면 개인 노트든 문제를 풀고나면 계속 자체적인 데이터베이스를 계속 쌓아두고 계시는걸 추천드립니다. 혹시 모르는 문제를 만났을 때 이전에 비슷한 문제를 풀어본 경험이 도움이 될 수가 있어서 그렇습니다.

 

코드(C++)

 

코드(Python)

 

코드(Java)