8/24 Problem Solving

9470 Strahler 순서 (G3)

 

위상 정렬을 하면 되는데 조건이 붙어있다. 노드로 들어오는 강의 순서 중 가장 큰 값을 cnt 배열을 두고 관리했다. 이 부분에서 구현이 조금 엉켜서 애먹었다.

 

http://boj.kr/bd1acde263c04d71bcdb47d6187cbce5

 

 

15483 최소 편집 (G3)

 

d[i][j] = 문자열 a의 첫 i개의 문자를 문자열 b의 첫 j개의 문자로 만드는데 필요한 최소 편집 횟수

 

만약 a의 i번째 문자와 b의 j번째 문자가 같다면 d[i][j] = d[i-1][j-1]이다. 문자가 다르다면 삽입, 삭제, 교체 세 가지 경우 중에서 최소값을 선택해서 테이블을 채운다.

 

http://boj.kr/c148fea9541c466d821362fc4404ad81

 

 

2655 가장높은탑쌓기 (G3)

 

dp[i] = i번째 벽돌을 탑의 가장 위에 놓았을 때 만들 수 있는 최대 탑 높이

 

벽돌들을 밑면의 넓이 기준으로 오름차순 정렬한다. 작은 밑면 넓이의 벽돌이 위에 쌓일 수 있도록 하기 위함이다. 현재까지 계산된 최대 탑 높이를 max_height에 갱신하고, 그 최상단 벽돌의 인덱스를 max_index에 저장한다. 그 다음에 max_index를 시작으로 trace 배열을 따라가면서 탑을 구성하는 벽돌들의 인덱스를 출력해주면 된다.

 

http://boj.kr/6cb1c81747434e269224b70d2780d6d7

 

 

17182 우주 탐사선 (G3)

 

이미 방문한 행성도 중복해서 갈 수 있으므로 경로 순서가 중요한 것은 아니다. Floyd-Warshall 알고리즘으로 모든 정점 쌍의 최단거리를 구해준다. 구해진 dist 테이블을 이용해서 백트래킹으로 모든 행성을 탐사하는데 걸리는 최소 시간을 계산해주면 된다.

 

http://boj.kr/555824188cf74aa59b36e6007b05d11f

 

 

1695 팰린드롬 만들기 (G3)

 

dp[i][j] = 수열의 i번째 원소부터 j번째 원소까지를 팰린드롬으로 만들기 위해 필요한 최소 삽입 횟수

 

팰린드롬의 정의를 이용하면 점화식을 이끌어 낼 수 있다.

dp[i][i]=0 : 한 개의 원소는 이미 팰린드롬이므로 삽입이 필요없다.

dp[i][i+1] : 두 개의 원소가 동일하면 0 다르면 1이다.

i번째 원소와  j번째 원소가 같다면 dp[i][j]=d[i+1][j-1]이다. 그렇지 않다면 dp[i][j] = min(dp[i+1][j],dp[i][j-1])+1로 계산한다.

 

http://boj.kr/1fa507f5633b4846a2b202e476ef3e4c