글 읽기 - 반례가 있을까요..?

inseu99 2년 전 0

2873번 문제인데,

가로세로 홀수인 경우는 무조건 모든 경우 탐색하면 되니 쉽고,

모두 짝수인 경우가 문제인데, (0,0) 에서 지그재그로 통하는 부분?이 아닌 부분중 최솟값을 빼고 탐색하면 되겠더라구요.

최솟값인 부분 (avoid로 선언함) 이 포함된 두 줄을 middle 로 놓고, 따로 구했는데요. (나머지는 그냥 출력하면 되구요.)

시간초과나 컴파일에어, 메모리 초과도 아니고, 그냥 '틀렸습니다' 라고 뜨는데, 도저히 생각해봐도 어디가 문제인지 모르겠습니다...

반례를 만들려고 해봐도 만들어지지가 않아요 ㅠㅠ 혹시 도움을 주신다면 정말 감사하겠습니다 흑

let setCoordinate = readLine()!.split(separator: " ").map { Int($0)! }
let x_max = setCoordinate[1]
let y_max = setCoordinate[0]

var matrix: [[Int]] = []
for _ in 0..<y_max {
    matrix.append(readLine()!.split(separator: " ").map { Int($0)! })
}

enum Direction {
    case Up
    case Down
    case Right
    case Left
}

var storage: [Direction: String] = [.Up: "U", .Down: "D", .Right: "R", .Left: "L"]

for _ in 2..<x_max {
    storage[.Right]! += "R"
    storage[.Left]! += "L"
}
for _ in 2..<y_max {
    storage[.Up]! += "U"
    storage[.Down]! += "D"
}

func printDirection(direction: Direction) {
    print(storage[direction]!, terminator: "")
}

func reverseDirection(direction: Direction) -> Direction {
    switch direction {
    case .Up:
        return .Down
    case .Down:
        return .Up
    case .Right:
        return .Left
    case .Left:
        return .Right
    }
}

func lrud(startDirection: Direction, repeatCount: Int) { //lrud -> left right up down
    let forward = startDirection    // 원하는 방향부터 돌아가며 count만큼 왔다갔다하는 함수
    let reverse = reverseDirection(direction: startDirection)
    if repeatCount < 0 { return }
    for i in 0..<repeatCount {
        i % 2 == 0 ? printDirection(direction: forward) : printDirection(direction: reverse)
        if repeatCount - 1 != i {
            startDirection == .Left || startDirection == .Right ?
            print("D", terminator: "") : print("R", terminator: "")
        }
    }
}

if x_max % 2 == 1 {
    lrud(startDirection: .Down, repeatCount: x_max)
} else if y_max % 2 == 1 {
    lrud(startDirection: .Right, repeatCount: y_max) // x_max or y_max 가 홀수일때는 모든 행렬 순회 가능
} else {
    var avoid = Int.max
    var avoidIndex = (x: 0, y: 0)

    for i in 0..<matrix.count {
        for j in stride(from: (i+1) % 2, to: x_max, by: 2) { // 둘 다 짝수일 때는 시작점의 지그재그 방향이 아닌 한 지점을 포기
            if matrix[i][j] < avoid {
                avoid = matrix[i][j]                    // 지그재그 방향에 없는 수 중 가장 작은 수를 피해야 함.
                avoidIndex = (x: j, y: i)
            }
        }
    }
    let middleSection = avoidIndex.y % 2 == 0 ? avoidIndex.y : avoidIndex.y-1 // avoid 가 있는 곳을 기준으로 세개의 섹션으로 나눈다. 어보이드 이전, 끼인 곳, 이후

    lrud(startDirection: .Right, repeatCount: middleSection) // 첫번째 section 출력
    if middleSection != 0 { print("D", terminator: "")} // 첫번째에 middle이 시작하지 않는다면 한칸 내려줌

    var middlePrint = ""
    for i in 0..<x_max-1 {
        if avoidIndex.x == i { middlePrint += "R" }
        middlePrint = i % 2 == 0 ? middlePrint + "D" : middlePrint + "U" //끼인 곳은 avoid 만나면 피해가도록 처리
        if i != x_max-2 { middlePrint += "R" }
    }
    if middlePrint.count < x_max*2-2 { middlePrint += "R" }  // 마지막 부분이 avoid일 경우를 위한 라인.
    print(middlePrint, terminator: "")
    if middleSection < y_max-1 { print("D", terminator: "")} // middle 로 끝나지 않는다면 한칸 내려줌.

    lrud(startDirection: .Left, repeatCount: y_max-middleSection-2) // 세번째 section 출력
}

inseu99 2년 전 0

마지막에 print("") 하니까 정답처리 되네요 ㅎㅎ.. 같은 문제로 고생하신다면 마지막에 줄바꿈 하시면 될수도 있어요

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

문제

문제

출처

ICPC

반례가 있을까요..?

inseu99 2년 전 0

inseu99 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말