이렇게 반드시 조건을 만족시키게 점화식을 구성하고, 초기 값부터 점화식을 만족하도록 설정하면 모든 항이 조건을 만족하게 된다.
그리고 점화식을 구성하면서 i-3까지 인덱스를 봐야 하길래, 3번째 포도주부터 반복문을 돌리기 위해 포도주 인덱스를 1부터 시작했다.
그리고 i를 3 ~ n까지 반복문을 돌려서 dp 값을 구하면, dp[n]이 답이 된다.
코드
import kotlin.math.max
fun main() {
val n = readLine()!!.toInt()
val wines = IntArray(n+2)
val dp = IntArray(n+2)
// 포도주 인덱스 1부터 시작
repeat(n){ i ->
wines[i+1] = readLine()!!.toInt()
}
// 초기값 설정
dp[1] = wines[1]
dp[2] = wines[1] + wines[2]
for (i in 3..n){
// 점화식
val maxWithCurrentWine
= max(dp[i-3] + wines[i-1] + wines[i], dp[i-2] + wines[i]) // i번째 와인을 마시는 경우 중 최대 값
dp[i]
= max(dp[i-1], maxWithCurrentWine) // i번째 와인을 마시는 or 안마시는 경우 중 최대 값
}
println(dp[n])
}
어떤 알고리즘을 써야할까 고민을 많이 했다. 정렬, 그리디, 백트래킹, ... 그래프 탐색? 예시를 보니까 (1번 - 3번)을 고르면 3번을 타고 들어가서 (3번 -1번)을 고르는 식으로, 왠지 그래프 탐색 아닐까 생각이 들었다. 하지만 풀이 방법이 확실하게 떠오르지 않았고 알고리즘 유형을 봤더니 dfs 문제였는데, 그걸로 어떻게 최대 개수로 같은 집합을 뽑게 만들라는 건지 여전히 감이 오지 않았다. 그래서 풀이 방법을 찾아봤는데, dfs를 통해 그래프 방문의 사이클을 찾아내는 문제였다.
사이클은 반드시 형성된다. 아랫줄의 번호들이 1~n이기 때문이다. 같은 숫자가 2번 나오든, n까지 하나씩 나오든 반드시 사이클이 형성되므로, 사이클을 형성하는 번호들을 모두 찾으면 그것이 답이다.
사실 이 문제 이해하려고 다른 사람들 코드도 많이 보고, 생각을 많이 했더니 뭐가 이해가 안됐는지 기억이 안난다. 내가 뭘 모르는지 아는 것도 어려운 거였다.
쓰리디핏님의 블로그(https://3dpit.tistory.com/12)를 참고했는데, 접근 방법을 보며 금방 이해할 수 있었다. 그리고 사실 약간 충격을 받았다, 내가 여태껏 수동적으로 문제를 풀고 있었구나... 앞으론 이해가 잘 안될 때는 직접 그림도 그려보고, 예시를 적극적으로 활용하면서 문제를 이해해봐야겠다고 반성했다.
사이클을 발견하는 문제란 건 알았는데, 어떻게 구현하는지도 문제였다. 가장 간결한 방법은 첫번째 줄에 있는 숫자들을 기준으로 1~n까지 하나씩 그래프 탐색을 하면서 (ex: 1을 시작으로 방문 -> 1은 3과 연결되어 있으므로 1을 방문 체크하고 3을 방문, 3을 방문 체크하고 연결되어 있는 1을 방문 ....) 사이클을 형성하는지 확인하는 것이다. 사이클은 반드시 형성되므로, 첫째줄에 있는 숫자들을 기준으로 방문 여부를 체크해서 중복 방문할 때 시작 번호에서 사이클이 형성되는지 확인하면 된다.
코드1이 이런 방식이다.
코드2는 위, 아래 줄의 방문한 번호들을 다 저장해가면서 푸는, 좀 더 직관에 가까운 풀이법이고,
코드3는 dfs는 스택으로도 풀 수 있을테니 시도해보다가, 단순하게 변수만 사용해도 구현이 가능하길래 변수로 스택을 사용한 것처럼 구현했다. 채점해보니 재귀보다 느렸다
이번 문제는 어렵게 느껴저서, 여러 코드를 읽어봤다. 복습에도, 문제 해결에 관한 사고력을 늘리는 데에도 도움이 많이 될 것 같아서 앞으로도 잘 안풀리는 문제들은 이렇게 공부하려고 한다.
코드1
fun main() {
val n = readLine()!!.toInt()
val secondLine = IntArray(n+1)
val answerList = mutableListOf<Int>()
repeat(n){ i ->
secondLine[i+1] = readLine()!!.toInt()
}
// 첫째 쭐의 번호들을 대상으로 사이클을 형성하는 숫자인지 확인한다.
for (i in 1..n){
val visited = Array(n+1){ false }.apply{ this[i] = true }
if(hasCycle(i, secondLine[i], visited, secondLine)){
answerList.add(i)
}
}
// 1부터 사이클을 확인했으므로 정렬하지 않아도 된다
println(answerList.size)
answerList.forEach{
println(it)
}
}
fun hasCycle(start: Int, current: Int, visited: Array<Boolean>, secondLine: IntArray): Boolean {
// 현재 번호를 처음 방문하는 거라면 방문 처리를 하고 연결된 다음 번호를 방문한다
if (visited[current].not()){
visited[current] = true
return hasCycle(start, secondLine[current], visited, secondLine)
}
// 중복 방문일 때, 탐색을 시작한 번호에서 사이클 시작된다 -> 사이클을 형성하는 번호(정답)이다
// 중간에 사이클이 형성된다 -> 정답이 아니다
return start == current
}
코드2
val answerList = mutableListOf<Int>()
fun main() {
val n = readLine()!!.toInt()
val secondLine = IntArray(n + 1)
val isAnswer = Array(n + 1) { false }
repeat(n) { i ->
secondLine[i + 1] = readLine()!!.trim().toInt()
}
for (i in 1..n) {
if (isAnswer[i]) continue
val visitedFirstLine = mutableSetOf<Int>()
val visitedSecondLine = mutableSetOf<Int>()
checkCycle(i, secondLine, visitedFirstLine, visitedSecondLine, isAnswer)
}
println(answerList.size)
answerList.sorted().forEach {
println(it)
}
}
fun checkCycle(
index: Int,
secondLine: IntArray,
visitedFirstLine: MutableSet<Int>,
visitedSecondLine: MutableSet<Int>,
isAnswer: Array<Boolean>
){
if (visitedFirstLine.contains(index)) {
return
}
visitedFirstLine.add(index)
visitedSecondLine.add(secondLine[index])
if (visitedFirstLine == visitedSecondLine){
visitedFirstLine.forEach { i ->
isAnswer[i] = true
answerList.add(i)
}
return
}
checkCycle(secondLine[index], secondLine, visitedFirstLine, visitedSecondLine, isAnswer)
}
코드3
fun main() {
val n = readLine()!!.toInt()
val secondLine = IntArray(n + 1)
val answerList = mutableListOf<Int>()
repeat(n) { i ->
secondLine[i + 1] = readLine()!!.trim().toInt()
}
for (startIndex in 1..n) {
val visited = Array(n + 1) { false }.apply { this[startIndex] = true }
var currentIndex = secondLine[startIndex]
while (true) {
if (!visited[currentIndex]) {
visited[currentIndex] = true
currentIndex = secondLine[currentIndex]
continue
}
if (startIndex == currentIndex) {
answerList.add(startIndex)
}
break
}
}
println(answerList.size)
answerList.forEach {
println(it)
}
}
fun main(){
var n = 0
var c = 0
val listOfHouse = mutableListOf<Int>()
readLine()!!.trim().split(" ").map{ it.toInt() }.let{
n = it[0]
c = it[1]
}
repeat(n){
listOfHouse.add(readLine()!!.toInt())
}
listOfHouse.sort() // 정렬: 이분탐색의 전제 조건
var lower = 1 // 최소 간격
var upper = listOfHouse.last() - listOfHouse[0] // 최대 간격: 양 끝 집 사이의 거리
var answer = upper
while(lower <= upper){
val mid = (lower + upper) / 2
var count = 1 // 공유기 설치한 횟수
var prevHouseIdx = 0 // 직전에 설치된 집
// mid보다 인접 간격이 길거나 같도록 설치한다
for(i in 1 until n){
if (listOfHouse[i] - listOfHouse[prevHouseIdx] >= mid){
count++
prevHouseIdx = i
}
}
// c == count -> 간격을 더 늘려도 모두 설치할 수 있는지 확인해본다
// c < count -> 더 많이 설치됐다 -> 설치 간격을 늘려본다
if (c <= count){
lower = mid + 1
answer = mid
}else{ // 더 많은 공유기를 설치해야 한다 -> 간격을 줄인다
upper = mid - 1
}
}
println(answer)
}
k-1 길이의 오르막 수에서 마지막 수보다 크거나 같은 수를 이어 붙이면 길이가 k인 오르막 수를 구할 수 있다.
ex) 123 -> 1233, 1234, ..., 1239
이렇게 수의 길이 k에 대해 직전 항으로 다음 항을 만들 수 있으므로 다이나믹 프로그래밍으로 문제를 해결할 수 있다.
길이 k와 마지막 자리 숫자 i로 점화식 dp를 정의하면,
dp[k][i]: 길이가 k이고, i로 끝나는 오르막 수
dp[k][i] = sum( dp[k-1][j] ), (0 <= j <= i)
코드
fun main(){
val n = readLine()!!.toInt()
val dp = Array(n+1){IntArray(10)}
// 길이가 1이고 i로 끝나는 오르막수
for (i in 0 until 10){
dp[1][i] = 1
}
// 길이 2~n까지 n-1번 반복
for (k in 2..n){
for (i in 0..9){
for (j in 0..i){
dp[k][i] = (dp[k][i] + dp[k-1][j]) % 10_007
}
}
}
println(dp[n].toList().reduce{acc, num -> (acc + num) % 10_007})
}