BOJ 9177 - 단어 섞기 문제 링크https://www.acmicpc.net/problem/9177 문제 해결 1. DP 문제. DP[i][j] = 처음 문자열의 i 인덱스까지와 두 번째 문자열의 j 인덱스까지 섞어서 만든 문자열이 비교할 문자열과 일치하는 가에 대한 값 저장. 주의할 점 || 생각해볼 점 1. 비교할 문자열의 처음부터 차례대로 비교하면 될 것이라고 생각하기 쉽다. 하지만 만약 처음 문자열과 두 번째 문자열이 같은 문자를 가진다면 어느 것을 골라야할 지 명확해지지 않는다. 그러므로 DP를 사용해서 문제를 해결해야한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 BOJ 9370 - 미확인 도착지 문제 링크https://www.acmicpc.net/problem/9370 문제 해결 1. 최단 거리를 구하는 문제. 2. 시작점과 도착점이 될 수 있는 후보 점들이 주어진다. 도착점이 되기 위해선, 반드시 g와 h 사이의 간선을 지나야한다. 3. dist1[i] = 시작점으로부터 모든 점까지의 최단 거리. dist2[i] = dist1[g]와 dist1[h] 중 가까운 점 g 또는 h로부터 모든 점까지의 최단 거리 4. 도착점이 될 수 있는 점 t가 있을 때, dist1[t] == dist1[min(dist1[g],dist1[h])인 점] + dist2[t] 이 되는 t를 오름차순으로 출력 주의할 점 || 생각해볼 점 1. testcase마다 graph를 초기화시키는 과정에서 실수가 있었다. 항상 조심.. 더보기 BOJ 2787 - 흔한 수열 문제 문제 링크https://www.acmicpc.net/problem/2787 문제 해결 1. 수열을 복원하기 전, chk[i][j] = i번 째 자리에 숫자 j가 위치할 지에 대한 check. 1이면 j가 i번 째에 있을 수 없음을 나타낸다. 2. 들어갈 수 있는 수들을 vector에 넣고 이분 매칭을 통해서 최대 매칭 수를 구한다. 3. 매칭 수가 N과 같다면 매칭된 수열을 출력. 그렇지 않다면 -1을 출력한다. 주의할 점 || 생각해볼 점 1. 이분 매칭을 통해서 문제를 해결할 수 있음을 알 수 있었다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 11 12 13 14 15 16 17 ··· 32 다음