솧로그

[백준] 1941. 소문난 칠공주

https://www.acmicpc.net/problem/1941 처음에는 5 X 5 그래프의 각 노드를 시작으로 그래프 탐색을 해서 7명을 모으는 것을 생각했다. 그런데 같은 조합이 여러 번 나올 수 있다. (학생 1 -> 2 -> 3인 조합과 학생 3 -> 2 -> 1의 조합은 같기 때문) 그리고 이때 이미 나온 조합인지 일일이 검사하는 건 매우 비효율적이다. 따라서 25명의 학생 중 7명의 학생 조합을 찾고(백트래킹), 이 조합의 학생들이 모두 연속된 자리인지, 그리고 S 값이 더 많은지 확인(bfs)하면 된다. 그런데 7명의 학생 조합을 찾을 때 중복된 조합을 생성하면 안된다. (ex, 학생 1 + 2, 학생 2 + 1은 같음) 따라서 5 X 5 배열을 숫자 0 ~ 24로 취급한 후, dfs의 s..

[백준] 7570. 줄 세우기

https://www.acmicpc.net/problem/7570 처음에 떠올렸던 풀이는 시간 초과로 불가능했다. 따라서 다른 방법을 떠올려야 하는데, 구글링을 통해 dp로 O(N)의 시간으로 풀 수 있는 방법을 발견했다. (https://mygumi.tistory.com/276#recentEntries)우선 숫자를 제일 앞이나 뒤로 이동시키는 최솟값 = (n - 가장 긴 연속된 숫자의 오름차순 수열의 길이)이다.그리고 가장 긴 연속된 숫자의 오름차순 수열의 길이를 찾기 위해선 다음 점화식이 사용된다.dp[n] = dp[n - 1] + 1혼자 힘으로 떠올리기 힘들고 이렇게 적어도 와닿지 않지만, 예시를 통해 직접 적어가며 생각하면 이해는 된다..import java.io.BufferedReader;imp..