백준 [17281] kotlin

[문제]

https://www.acmicpc.net/problem/17281

17281번: ⚾

주의 : 코틀린으로 풀 때, 베이스를 배열에 저장해놓고 풀게 되면, 시간초과가 발생합니다.

[풀이]

- 문제 설명

문제를 이해를 잘못해서 한 번 삽질하고, 시간초과 때문에 두 번 고생한 문제이다.

 

간단하게 요약을 하면, 

입력값 N은 이닝 수 이다. 이닝 수는 야구로 생각하면 1회초, 1회말의 그 1회를 의미한다.

입력으로 들어온 이닝 수 만큼 경기를 진행했을 때, 얻을 수 있는 최고점을 기록하는 문제이다.

 

선수는 총 9명으로 고정되어 있고, 각 선수가 해당 이닝에서 얻을 수 있는 점수를 두번째 열부터 입력으로 주어진다.

 

- 풀이

DFS를 이용하여 풀었다.

1~9까지 순서로 각 숫자마다 타자를 저장해 놓은 배열 lineUp과 

DFS 탐색을 위해 이미 방문한 곳은 방문하지 않아야 하므로, 상태를 저장해놓은 visit 배열을 사용한다.

 

특히 4번타자는 1번으로 타자 자리에 선다는 조건이 있으므로, 

lineUp[3] = 0
visit[3] = true

dfs 함수를 호출하기 전에 다음과 같이 설정해야 한다.

 

dfs 과정은 다음과 같다.

fun dfs(cnt : Int)
{
    if(cnt == 9)
    {
        cal()
        return
    }
    for(i in 0 until lineUp.size)
    {
        if(visit[i]) continue
        visit[i] = true
        lineUp[i] = cnt
        dfs(cnt + 1)
        visit[i] = false
    }
}

cnt의 경우에는 타자이다. cnt가 0인경우 1번타자를 의미한다.

cnt가 9에 도달할 경우 9개의 타자가 모두 lineUp배열에 저장이 되었기 때문에 점수를 계산하는 cal() 함수를 호출한다.

 

그게 아닐 경우에는 

for-구문을 돌면서, 방문한지 체크를 하고, 방문하지 않았을 경우에는 값을 저장해주고, dfs를 다시 호출해준다. 

그리고 다시 방문을 초기화해줌으로써 순열을 만들어준다.

 

- 점수 계산

점수 계산은 처음에 각 1루, 2루,3루를 base라는 이름의 배열에 저장하여 사용했는데 시간 초과가 발생하였다.

1루를 base1, 2루를 base2, 3루를 base3로 따로 지정해주어 제출하였더니 정답처리 되었다.

 

중요한 점은 아래와 같다.

1. 아웃 카운트가 3이 될 때까지 해당 이닝의 선수 라인업이 계속 반복이 된다

2. 해당 이닝이 끝나면, 끝날 때 선수의 다음에 오는 선수가 다음 이닝에 1번 주자로 나오게 된다.

 

위를 주의하여 코드를 작성하면 아래와 같다.

fun cal()
{
    var tmp = 0
    var status = false
    var score = 0

    repeat(N)
    {
        i ->
        var out = 0
        status = false

        var base1 = 0
        var base2 = 0
        var base3 = 0

        while(!status)
        {
            while (tmp < lineUp.size){
                val player = baseball[i][lineUp[tmp]]
                when(player)
                {
                    0 -> {
                        out++
                    }
                    1 -> {
                        score += base3
                        base3 = base2
                        base2 = base1
                        base1 = 1
                    }
                    2 -> {
                        score += (base3 + base2)
                        base3 = base1
                        base2 = 1
                        base1 = 0
                    }
                    3 -> {
                        score += (base3 + base2 + base1)
                        base1 = 0
                        base2 = 0
                        base3 = 1
                    }
                    4 -> {
                        score += (base3 + base2 + base1 + 1)
                        base1 = 0
                        base2 = 0
                        base3 = 0
                    }
                }
                tmp++
                tmp %= 9
                if(out == 3) {
                    out = 0
                    status = true
                    break
                }
            }
        }
        ans = max(ans , score)
    }
}

[전체 코드]

 

import java.io.BufferedReader
import java.io.BufferedWriter
import java.io.InputStreamReader
import java.io.OutputStreamWriter
import kotlin.math.max

var N = 0
var ans = 0
lateinit var baseball : Array<MutableList<Int>>
val lineUp = MutableList<Int>(9){-1}
val visit = MutableList<Boolean>(9){false}

fun main() {
    val br = BufferedReader(InputStreamReader(System.`in`))
    val bw = BufferedWriter(OutputStreamWriter(System.out))

    N = br.readLine().toInt()
    baseball = Array(N){ mutableListOf() }

    repeat(N)
    {
        i ->
        baseball[i] = br.readLine().split(" ").map { it.toInt()} as MutableList<Int>
    }

    lineUp[3] = 0
    visit[3] = true
    dfs(1)
    bw.write(ans.toString())
    bw.flush()
    bw.close()
}

fun dfs(cnt : Int)
{
    if(cnt == 9)
    {
        cal()
        return
    }
    for(i in 0 until lineUp.size)
    {
        if(visit[i]) continue
        visit[i] = true
        lineUp[i] = cnt
        dfs(cnt + 1)
        visit[i] = false
    }
}

fun cal()
{
    var tmp = 0
    var status = false
    var score = 0

    repeat(N)
    {
        i ->
        var out = 0
        status = false

        var base1 = 0
        var base2 = 0
        var base3 = 0

        while(!status)
        {
            while (tmp < lineUp.size){
                val player = baseball[i][lineUp[tmp]]
                when(player)
                {
                    0 -> {
                        out++
                    }
                    1 -> {
                        score += base3
                        base3 = base2
                        base2 = base1
                        base1 = 1
                    }
                    2 -> {
                        score += (base3 + base2)
                        base3 = base1
                        base2 = 1
                        base1 = 0
                    }
                    3 -> {
                        score += (base3 + base2 + base1)
                        base1 = 0
                        base2 = 0
                        base3 = 1
                    }
                    4 -> {
                        score += (base3 + base2 + base1 + 1)
                        base1 = 0
                        base2 = 0
                        base3 = 0
                    }
                }
                tmp++
                tmp %= 9
                if(out == 3) {
                    out = 0
                    status = true
                    break
                }
            }
        }
        ans = max(ans , score)
    }
}