글 읽기 - 21608 반례 부탁드립니다.

960722rjsdn 2년 전 0

입력을 받아 인접한 칸의 좋아하는 사람의 수, 빈칸의 개수를 세서 비교하여 앉을 자리를 찾도록 했습니다.

제출하면 2%에서 틀렸습니다가 나옵니다. 몇 가지 테스트 케이스를 만들어서 시도해봤는데도 맞습니다.

반례나 미처 생각하지 못한 부분을 알려주시면 감사하겠습니다🙏

dr = [1, 0, -1, 0]
dc = [0, 1, 0, -1]

def sitting(num, likes):
    # 좋아하는 학생이 인접한 칸에 가장 많은 칸 확인
    likeNum = 0
    num_r, num_c = 0, 0
    for r in range(N):
        for c in range(N):
            if sit[r][c] == 0:
                temp = 0
                for i in range(4):
                    nr = r + dr[i]
                    nc = c + dc[i]
                    if 0 <= nr < N and 0 <= nc < N:
                        if sit[nr][nc] in likes:
                            temp += 1
                if likeNum < temp:
                    likeNum = temp
                    num_r, num_c = r, c
                # 인접하는 칸 중 좋아하는 학생의 수가 같으면
                if likeNum == temp:
                    # 인접한 칸 중 비어있는 칸이 더 많은 경우에만 변경
                    if emp_sit[r][c] > emp_sit[num_r][num_c]:
                        num_r, num_c = r, c
                    elif emp_sit[r][c] == emp_sit[num_r][num_c] and sit[num_r][num_c] != 0:
                        num_r, num_c = r, c

    sit[num_r][num_c] = num
    # 인접하는 칸에서 비어있는 칸의 개수 -1
    for i in range(4):
        nr = num_r + dr[i]
        nc = num_c + dc[i]
        if 0 <= nr < N and 0 <= nc < N:
            emp_sit[nr][nc] -= 1


N = int(input())
sit = [[0] * N for _ in range(N)]
emp_sit = [[0] * N for _ in range(N)]

# 비어있는 칸의 개수 세기
for r in range(N):
    for c in range(N):
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                emp_sit[r][c] += 1

# 자리에 앉히기
like_students = [[] for _ in range(N ** 2 + 1)]
for i in range(N ** 2):
    data = list(map(int, input().split()))
    sitting(data[0], data[1:])
    like_students[data[0]].extend(data[1:])

# 만족도 구하기
ans = 0
for r in range(N):
    for c in range(N):
        temp = 0
        for i in range(4):
            nr = r + dr[i]
            nc = c + dc[i]
            if 0 <= nr < N and 0 <= nc < N:
                if sit[nr][nc] in like_students[sit[r][c]]:
                    temp += 1

        if temp == 0:
            continue
        else:
            ans += 10 ** (temp-1)

print(ans)

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

문제

문제

출처

ICPC

21608 반례 부탁드립니다.

960722rjsdn 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말