문제 링크
문제 요약
N x N 크기의 정방 행렬이 주어집니다. 이 행렬이 다음 조건을 만족하는지 확인해야 합니다:
- 행렬의 모든 요소는 음수가 아니어야 합니다 (0 이상).
- 각 행에 대해, 해당 행의 주 대각선 요소(A[i][i])는 그 행의 나머지 모든 요소들의 합보다 크거나 같아야 합니다. 즉,
A[i][i] >= sum(A[i][j] for j != i)여야 합니다.
위 두 가지 조건을 모두 만족하면서, 추가적으로 적어도 하나의 행이 엄격한 대각선 우세 조건 (A[i][i] > sum(A[i][j] for j != i)) 을 만족하는 경우, “YES”와 함께 엄격한 대각선 우세 조건을 만족하는 행의 개수를 출력합니다.
만약 두 가지 조건 중 하나라도 만족하지 않거나, 두 조건을 모두 만족하더라도 엄격한 대각선 우세 조건을 만족하는 행이 하나도 없다면 “NO”를 출력합니다.
풀이
이 문제는 주어진 행렬이 특정 대각선 우세 조건을 만족하는지 확인하고, 엄격한 우세 조건을 만족하는 행의 개수를 세는 구현 문제입니다.
풀이 과정은 다음과 같습니다:
- 입력 처리: 먼저 행렬의 크기
N과N x N크기의 행렬을 입력받습니다. - 음수 요소 확인: 행렬의 모든 요소를 순회하면서 하나라도 음수가 발견되면, 문제의 첫 번째 조건을 만족하지 못하므로 즉시 “NO”를 출력하고 종료합니다.
- 대각선 우세 조건 확인:
- 엄격한 대각선 우세 조건을 만족하는 행의 개수를 세기 위한 카운터
strict_dominant_count를 0으로 초기화합니다. - 각 행
i(0부터N-1까지)에 대해 다음을 수행합니다:- 해당 행
i의 주 대각선 요소l[i][i]를 제외한 나머지 요소들의 합row_sum_excluding_diagonal을 계산합니다. - 약한 대각선 우세 조건 확인:
l[i][i]가row_sum_excluding_diagonal보다 작다면 (즉,l[i][i] < row_sum_excluding_diagonal), 문제의 두 번째 조건을 만족하지 못하므로 즉시 “NO”를 출력하고 종료합니다. - 엄격한 대각선 우세 조건 확인:
l[i][i]가row_sum_excluding_diagonal보다 크다면 (즉,l[i][i] > row_sum_excluding_diagonal),strict_dominant_count를 1 증가시킵니다.
- 해당 행
- 엄격한 대각선 우세 조건을 만족하는 행의 개수를 세기 위한 카운터
- 결과 출력: 모든 행에 대한 검사를 마친 후,
strict_dominant_count가 0보다 크다면 (즉, 엄격한 대각선 우세 조건을 만족하는 행이 하나라도 있다면) “YES”와 함께strict_dominant_count값을 출력합니다. 그렇지 않다면 (모든 조건은 만족했지만 엄격한 대각선 우세 행이 없다면) “NO”를 출력합니다.
이러한 과정을 통해 문제에서 요구하는 모든 조건을 효율적으로 검사할 수 있습니다.
정답 코드
def solve():
n = int(input())
l = [[*map(int,input().split())] for _ in range(n)]
# 1. 모든 요소가 음수가 아닌지 확인
for i in range(n):
for j in range(n):
if l[i][j] < 0:
return (False, -1) # 음수 발견 시 바로 NO
cnt = 0 # 엄격한 대각선 우세 조건을 만족하는 행의 개수
# 2. 각 행에 대해 대각선 우세 조건 확인
for i in range(n):
sm = 0
# 주 대각선 요소를 제외한 나머지 요소들의 합 계산
for j in range(n):
if i == j: # 주 대각선 요소는 합계에서 제외
continue
sm += l[i][j]
# 약한 대각선 우세 조건 확인: l[i][i] >= sm 이어야 함.
# 만약 l[i][i] < sm 이면 조건 불만족 -> NO
if sm > l[i][i]:
return (False, -1)
# 엄격한 대각선 우세 조건 확인: l[i][i] > sm 이면 cnt 증가
if sm < l[i][i]:
cnt += 1
# 모든 조건을 만족하고, 엄격한 대각선 우세 행이 하나라도 있는 경우
if cnt > 0:
return (True, cnt)
# 모든 조건은 만족했으나 엄격한 대각선 우세 행이 없는 경우 (cnt == 0)
return (False, -1)
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()
if ret[0]:
print("YES")
print(ret[1])
else:
print("NO")