- 문제 설명 - 문제 풀이 DFS를 사용해야 하는 문제이다. 그러나 단순히 DFS만 사용해서 풀면 탐색의 양이 무수히 많아지기 때문에 시간초과가 발생한다. 때문에 DFS + DP 메모제이션을 추가로 활용해줘야 하는 문제이다. 우선 상하좌우를 검색할때 현재 노드보다 값이 작은 곳만 향할 수 있어야 하기 때문에 배열의 크기를 arr[502][502]로 해주고, 최대값이 10000이므로 10001로 초기화 해주었다. 예제로 예시를 든다면 아래 표와 같이 나타낼 수 있다. 10001 10001 10001 10001 10001 10001 10001 10001 50 45 37 32 30 10001 10001 35 50 40 20 25 10001 10001 30 30 25 17 28 10001 10001 27 24..
- 문제 설명 - 문제 풀이 문제가 간단해 보이는듯 하면서도 배열을 적어보지 않으면 규칙을 찾기가 꽤 까다로웠다. 이 문제는 2차원 배열을 이용하여 풀어낼 수 있다. 이를 DP로 한다 하고 크기를 첫째 줄의 문자열의 길이 x 둘째 줄의 문자열의 길이로 해 선언해 준다. 이를 DP[i][j]라 했을때 0부터 i번째 문자열과 0부터 j번째 문자열 까지의 공통 부분 수열의 갯수를 넣어준다. 예제와 같이 ACAYKP, CAPCAK를 예로 든다면 아래 표와 같다. 행열의 첫째 줄은 0으로 한다고 가정하자. 형광칠 된 곳은 i번째 문자와 j번째 문자가 같은 지점이다. 표를 보면 규칙을 찾을 수 있는데 1. i번째 문자와 j번째 문자가 같다면 DP[i-1][j-1] + 1 을 한 것과 같다는 규칙 (대각선 위의 DP..
- 문제 설명 - 문제 풀이 처음에 문제 설명을 볼때 문제 자체를 이해하는데 은근 오래 걸렸다. 간단하게 설명해서, 길이가 1이면 1, 2, 3, 4, 5, 6, 7, 8, 9 로 9개 있다.(0으로 시작하는건 제외) 길이가 2이면 10, 21, 12, 32, 23, 43, 34, 54, 45, 65, 56, 76, 67, 87, 78, 98, 89로 총 17개가 있다. 여기서 중요하게 봐야할 점은 첫째 자리 수이다. 보면 0부터 시작해서 9로 끝나는 첫 째 자리 수를 순서대로 나열했는데, 이를 이용해 2차원 배열을 만들 수 있다. 길이 by 첫 째 자릿 수로 배열을 만들면 길이가 N이라고 할때 배열의 크기는 DP[N][10] 이 된다. 이때 편의상 코드에서는 DP[N+1][10]으로 해두겠다. 아래 그..
