글 읽기 - 뭐가 문제일까요? 틀렸습니다가 바로 뜨네요..

qwer15417 2년 전 0

꽤 조잡하지만 예시와 질문에 있는 반례는 모두 통과했습니다.

하지만 틀렸다고 뜨네요. 뭐가 문제일까요?

친한 친구, 빈 자리 고려해서 코드를 짰고 행1열1, 행1열2, 행1열3, 행2열1... 이런식으로 조사를 시작했기 때문에 행과 열 부분은 따로 조건문 코딩을 안해도 된다 생각했습니다.

잘못된 부분 있으면 지적 부탁드립니다!

import sys

N = int(sys.stdin.readline())
seats = [[-1] * (N + 2) for i in range(N+2)]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        seats[i][j] = 0

# 자리 앉히기
students = list()
for k in range(N * N):
    students.append(list(map(int, sys.stdin.readline().split())))
    location = (0, 0)
    best_friends = 0
    best_blanks = 0

    for i in range(1, N + 1):
        for j in range(1, N + 1):
            friends = 0
            blanks = 0
            # 상하좌우 조사
            if seats[i - 1][j] in students[k][1:]:
                friends += 1
            elif seats[i - 1][j] == 0:
                blanks += 1

            if seats[i + 1][j] in students[k][1:]:
                friends += 1
            elif seats[i + 1][j] == 0:
                blanks += 1

            if seats[i][j - 1] in students[k][1:]:
                friends += 1
            elif seats[i][j - 1] == 0:
                blanks += 1

            if seats[i][j + 1] in students[k][1:]:
                friends += 1
            elif seats[i][j + 1] == 0:
                blanks += 1

            # 최적일 경우
            if seats[i][j] == 0:
                if friends > best_friends:
                    best_friends = friends
                    best_blanks = blanks
                    location = (i, j)
                elif friends == best_friends:
                    if blanks > best_blanks:
                        best_blanks = blanks
                        location = (i, j)

    seats[location[0]][location[1]] = students[k][0]

# 만족도 구하기
score = 0
num = 0
for i in range(1, N + 1):
    for j in range(1, N + 1):
        num = 0
        for k in range(N*N):
            if seats[i][j] == students[k][0]:
                case = students[k][1:]
        if seats[i - 1][j] in case:
            num += 1

        if seats[i + 1][j] in case:
            num += 1

        if seats[i][j - 1] in case:
            num += 1

        if seats[i][j + 1] in case:
            num += 1
        if num == 1:
            score += 1
        elif num == 2:
            score += 10
        elif num == 3:
            score += 100
        elif num == 4:
            score += 1000
print(score)

pichulia 2년 전 14

문제의 조건을 만족하면서 이 코드를 틀리게 만드는 반례입니다.

pichulia 2년 전 1

friends 와 blanks 가 모두 0 일 때가 최적이 될 수 있습니다.

qwer15417 2년 전 0

"주변에 친구가 없고 빈 자리도 없는 경우"를 고려하지 못했네요.

도움주셔서 감사합니다!!!

coding_data_pul 2년 전 0

참고하세요, 아래 예제의 답은 4000 입니다.

daniel0801 2년 전 16

위 예제는 '어떤 학생이 좋아하는 학생 4명은 모두 다른 학생으로 이루어져 있다. 입력으로 주어지는 학생의 번호, 좋아하는 학생의 번호는 N²보다 작거나 같은 자연수이다. 어떤 학생이 자기 자신을 좋아하는 경우는 없다.'를 위반하는 테케가 아닌가요?

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

문제

문제

출처

ICPC

뭐가 문제일까요? 틀렸습니다가 바로 뜨네요..

qwer15417 2년 전 0

pichulia 2년 전 14

pichulia 2년 전 1

qwer15417 2년 전 0

coding_data_pul 2년 전 0

daniel0801 2년 전 16

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말