BOJ 문제풀이(W24)

2098 외판원 순회

 

2617 구슬찾기

구슬의 대소관계를 이용하여 그래프를 만들고, 이를 탐색하여 문제를 해결했습니다.

1번 구슬이 2번 구슬보다 무겁다면 1에서 2로 가는 간선을 그어주고 각각의 구슬에 대해 dfs를 돌려 그 구슬보다 무거운 구슬의 숫자를 셌습니다.

 

9009 피보나치

어떤 정수에서 그 정수보다 작은 피보나치 수열 중 가장 큰 피보나치수를 하나씩 빼주면서 문제를 해결했습니다.

 

5582 공통 부분 문자열

dp[i][j] := s[i]=t[j]이면서 이를 끝으로 하는 최대 공통 부분 문자열의 길이

이렇게 배열을 정의하면 쉽게 해결 할 수 있습니다.

주어진 두 문자열의 길이가 4,000이라 시간안에 풀 수 있습니다.

 

9251 LCS

최장 공통 부분 수열을 찾아주는 문제입니다.

수열을 찾아주는 문제라 무조건 바로 전의 문자와 비교하는 식으로는 해결이 어렵습니다.

dp[i][j] := S[:i], T[:j] 사이 LCS의 길이

이렇게 배열을 정의하고 배열을 채워야 합니다.

 

2075 N번째 큰 수

PQ를 이용하여 문제를 해결했습니다.

주어진 숫자들을 push하면서 N보다 크면 pop을 해주면 됩니다.

 

14881 물통 문제

용량이 10억이라 그래프 탐색으로는 시간안에 해결 할 수 없습니다.

문제를 해결하기 위해서는 최대공약수의 배수가 되는 용량에 대해서는 항상 만들어 줄 수 있다는 관찰이 필요합니다.

 

11062 카드게임

dp[i][j] := i~j까지 카드가 있을 때, 첫 턴을 시작하는 사람이 얻을 수 있는 최대 점수

이렇게 정의하고 문제를 해결하면 됩니다.

dp배열 정의가 상당히 어렵습니다.