글 읽기 - 두 코드의 차이가 무엇인지 궁금합니다.

bsgreentea 4년 전 0

1079 문제를 푸는 과정에서 궁금한 점이 생겨 질문드립니다.

두 가지 방식으로 제출을 했는데, 두 방식의 유일한 차이는 참가자의 유죄 지수를 나타내는 crime 배열의 위치입니다.

(하단에 맞았습니다를 받은 코드와 틀렸습니다를 받은 코드를 차례로 올려두었습니다.)

맞았습니다를 받은 첫 번째 코드의 경우는 crime 배열을 전역으로 선언하였고(,10, 48 ~ 50번째 줄),

틀렸습니다를 받은 두 번째 코드의 경우는 game() 함수 내에서 crime 배열을 temp라는 배열로 옮겨 사용했습니다(117, 118번째 줄).

두 번째 방식이 왜 틀렸는지를 도저히 못찾겠습니다.

무슨 차이가 있어서 결과가 다르게 나오는지 궁금합니다. 코드 한 번 봐주시면 감사하겠습니다ㅜㅜ

// 맞은 소스

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max

val br = BufferedReader(InputStreamReader(System.`in`))

var r = Array<IntArray>(20) { IntArray(20) }
var crime = IntArray(20)
var ans = 0

// state : 참가자의 죽음,생존 여부를 각각 1,0으로 표현
// n : 참가자의 수
// me : 은진이의 참가자 번호
// alive : 밤이 몇번 지났는지
// rem : 현재까지 생존한 참가자의 수
fun game(state: Int, n: Int, me: Int, alive: Int, rem: Int) {

    if (rem % 2 == 1) {

        var now = Int.MIN_VALUE
        var idx = 0

        for (i in 0 until n) {
            if (crime[i] > now && (1 shl i) and state == 0) {
                now = crime[i]
                idx = i
            }
        }

        if (idx == me) {
            ans = max(ans, alive)
            return
        }

        game(state or (1 shl idx), n, me, alive, rem - 1)

    } else {

        if (rem == 2) {
            ans = max(ans, alive + 1)
            return
        }

        for (i in 0 until n) {
            if (i != me && (1 shl i) and state == 0) {
                for (j in 0 until n) crime[j] += r[i][j]
                game(state or (1 shl i), n, me, alive + 1, rem - 1)
                for (j in 0 until n) crime[j] -= r[i][j]
            }
        }
    }
}

fun main() {

    var n = br.readLine().toInt()
    crime = br.readLine().split(' ').map { it.toInt() }.toIntArray()

    for (i in 0 until n)
        r[i] = br.readLine().split(' ').map { it.toInt() }.toIntArray()

    var me = br.readLine().toInt()

    br.close()

    if (n > 1)
        game(0, n, me, 0, n)

    println(ans)
}

// ================================================================================

// 틀린 소스

import java.io.BufferedReader
import java.io.InputStreamReader
import java.lang.Integer.max

val br = BufferedReader(InputStreamReader(System.`in`))

var r = Array<IntArray>(20) { IntArray(20) }
var ans = 0

fun game(state: Int, n: Int, me: Int, alive: Int, rem: Int, crime: IntArray) {

    if (rem % 2 == 1) {

        var now = Int.MIN_VALUE
        var idx = 0

        for (i in 0 until n) {
            if (crime[i] > now && (1 shl i) and state == 0) {
                now = crime[i]
                idx = i
            }
        }

        if (idx == me) {
            ans = max(ans, alive)
            return
        }

        game(state or (1 shl idx), n, me, alive, rem - 1, crime)

    } else {

        if (rem == 2) {
            ans = max(ans, alive + 1)
            return
        }

        for (i in 0 until n) {
            if (i != me && (1 shl i) and state == 0) {
                var temp = crime                        // <=====================
                for (j in 0 until n) temp[j] += r[i][j] // <=====================
                game(state or (1 shl i), n, me, alive + 1, rem - 1, temp)
            }
        }
    }
}

fun main() {

    var n = br.readLine().toInt()
    var crime = br.readLine().split(' ').map { it.toInt() }.toIntArray()

    for (i in 0 until n)
        r[i] = br.readLine().split(' ').map { it.toInt() }.toIntArray()

    var me = br.readLine().toInt()

    br.close()

    if (n > 1)
        game(0, n, me, 0, n, crime)

    println(ans)
}

shw2495 3년 전 1

이미 아실 것 같지만 밑의 코드가 틀린 이유는 temp=crime할 때 값을 copy하는 것이 아닌 temp가 crime 배열을 가리켜서(즉, temp 배열과 crime 배열이 같아서) temp가 바뀌면 crime도 같이 바뀌기 때문입니다.

118번 줄 다음에 temp와 crime 메모리 값을 출력해보면 정확히 같은 것을 알 수 있을 것입니다. (혹은 값을 출력해보면 temp가 바뀜에 따라 crime도 바뀌는 것을 알 수 있을 것입니다.)

bsgreentea 3년 전 0

친절한 답변 감사합니다!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

두 코드의 차이가 무엇인지 궁금합니다.

bsgreentea 4년 전 0

shw2495 3년 전 1

bsgreentea 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말