백준 28706번
https://www.acmicpc.net/problem/28706

문제

---

생각하기

---

• DP 문제이다.

  • 모듈러 연산을 통해서 7의 배수 값을 찾을 수 있다.

• 메모이제이션을 사용해서 통해서 이미 방문한 방향으로는 탐색하지 않는 가지치기를 진행한다.

  • flag를 통해서 재귀 가지치기를 할 수 도 있다.

동작

private fun calc(depth: Int, num: Int) {
    if (depth == N) {
        // 선택지를 모두 고른 이후 결과로 나온 결과가 7의 배수인지 확인

        if (num == 0) flag = true // 7의 배수가 맞으면 flag를 true로 지정
        return
    }

    if (memo[depth][num] || flag) {
        // 해당 깊이의 num을 이미 방문했거나 flag가 true일 경우 답을 찾았으므로 return
        return
    }

    memo[depth][num] = true // 방문처리

    if (cmd[depth].op1 == '+') {
        calc(depth + 1, (num + cmd[depth].num1) % 7)
    } else {
        calc(depth + 1, (num * cmd[depth].num1) % 7)
    }

    if (cmd[depth].op2 == '+') {
        calc(depth + 1, (num + cmd[depth].num2) % 7)
    } else {
        calc(depth + 1, (num * cmd[depth].num2) % 7)
    }
} // End of calc()

재귀를 통해서 구현했다

선택지를 모두 골라야하므로 최대 깊이는 N이 된다.

가지치기를 하기 위해서 메모이제이션을 사용한다.
memo[depth][num] 재귀 depth깊이의 num을 이미 방문한 경우는 진행하지 않는다.

모듈러 연산을 사용한다

결과

코드

---

Kotlin

import java.io.*
import java.util.*
import kotlin.math.max

// input
private lateinit var br: BufferedReader
private lateinit var sb: StringBuilder

// variables
private var N = 0
private var flag = false
private lateinit var cmd: Array<Operation>
private lateinit var memo: Array<BooleanArray>

private data class Operation(var op1: Char, var num1: Int, var op2: Char, var num2: Int)

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

    val t = br.readLine().toInt()
    repeat(t) {
        input()

        solve()
    }

    bw.write(sb.toString())
    bw.close()
} // End of main()

private fun solve() {
    calc(0, 1)

    when (flag) {
        true -> {
            sb.append("LUCKY")
        }

        else -> {
            sb.append("UNLUCKY")
        }
    }
    sb.append('\n')
} // End of solve()

private fun calc(depth: Int, num: Int) {
    if (depth == N) {
        // 선택지를 모두 고른 이후 결과로 나온 결과가 7의 배수인지 확인

        if (num == 0) flag = true // 7의 배수가 맞으면 flag를 true로 지정
        return
    }

    if (memo[depth][num] || flag) {
        // 해당 깊이의 num을 이미 방문했거나 flag가 true일 경우 답을 찾았으므로 return
        return
    }

    memo[depth][num] = true // 방문처리

    if (cmd[depth].op1 == '+') {
        calc(depth + 1, (num + cmd[depth].num1) % 7)
    } else {
        calc(depth + 1, (num * cmd[depth].num1) % 7)
    }

    if (cmd[depth].op2 == '+') {
        calc(depth + 1, (num + cmd[depth].num2) % 7)
    } else {
        calc(depth + 1, (num * cmd[depth].num2) % 7)
    }
} // End of calc()

private fun input() {
    N = br.readLine().toInt()
    flag = false

    memo = Array(N) { BooleanArray(7) }
    cmd = Array(N) { Operation(' ', 0, ' ', 0) }

    for (i in 0 until N) {
        val temp = br.readLine()
        cmd[i] = Operation(temp[0], temp[2] - '0', temp[4], temp[6] - '0')
    }
} // End of input()