# D6

1c2

SWEA 1855 LCA알고리즘을 사용하여 최소공통 조상을 구하는 알고리즘이다. 처음에 LCA알고리즘을 몰라서 한칸씩 부모를 타고 올라가 시간 초과가 났던 문제이다. LCA란? 아이디어를 간단하게 요약하면 다음과 같다 >* 트리 구조체에서 자신의 2의 거듭제곱번째 조상을 dp배열에 저장한다. > > * 특정한 두 노드의 최소 공통 조상을 찾을 때 dp배열을 활용하여 1칸->2칸->4칸 ...씩 타고 올라간다. 일단 dp배열을 생성하는 코드는 다음과 같다 i 의 $$2^j$$번째 조상은 i의 $$2^j-1$$번째 조상의 $$2^j-1$$번째 조상이다 라고 이해하면 된다. 영준이가 방문할 노드는 BFS를 따라가기 때문에 Queue에 방문 순서를 넣어 이를 구현하였다

wlstkd5129

[문제풀이] dp테이블의 크기를 12로 생성하여 index를 0부터 11까지로 사용해서 풀어보려고 했지만 1월일때의 dp테이블을 어떻게 갱신해줘야할지 생각이 안나서 테이블 크기를 13으로 하여 index를 0부터 12까지로 정의한 다음 1월일 때 인덱스 에러를 방지하기 위해 0의 index까지 사용했다. 먼저 1일 이용권과 1달 이용권을 사용했을 때의 dp테이블을 먼저 갱신해준 뒤, 3달을 포함할 수 있는 월이면(index가 3이상일 때) 3달 이용권을 사용했을 때의 dp테이블을 1일 이용권, 1달 이용권으로 갱신한 dp테이블과 비교하여 더 작은 값으로 해당 월의 dp테이블을 갱신해준다. 그 후, 맨 마지막 인덱스 dp테이블 값과 1년 이용권 사용할 때의 요금과 비교하여 더 적은 비용이 드는 값을 출력해준다.(1년 이용권과 비교해주는 이유는 1월부터 12월의 이용한 횟수와 관계없이 언제든지 이용이 가능하기 때문이다.) ※ DP방식이 아닌 DFS로도 풀 수 있지만 DP로