[BOJ] 백준 11811번 Python

백준 11811번 Python

https://www.acmicpc.net/problem/11811

 

문제

---

젊은 제다이 이번의 임무는 데스타에 침투하여 파괴하는 일이다.

데스타를 파괴하기 위해서는 길이 N의 음이 아닌 정수 수열 a_i가 필요하다.

그러나 이번은 이 수열을 가지고 있지 않다.

대신 그에게는 오랜 친구 다스 베이더에게 받은 쪽지가 하나 있다.

이 쪽지에는 그 수열이 만족해야 하는 조건이 적혀 있다.

이 쪽지에는 크기 N의 정사각 행렬이 있는데, i번째 행 j번째 열에 적힌 숫자는 a_i와 a_j에 비트연산 and를 수행한 결과값이다.

하지만 안타깝게도 광선검에 의해 쪽지가 손상되었고 이번은 행렬의 주 대각선에 있는 숫자를 읽을 수 없게 되었다.

원래 배열을 재구성하여 임무를 수행해야 하는 이번을 도와주자.

답은 유일하지 않을 수 있지만, 항상 존재하도록 주어진다.

 

 

입력

---

입력의 첫 번째 줄에는 행렬의 크기 N (1 ≤ N ≤ 1 000)이 주어진다.

다음 N개의 줄에는 행렬의 각 원소인 N개의 숫자 m_ij (1 ≤ m_ij ≤ 10⁹)가 주어진다.

 

 

출력

---

정확히 한 줄에 문제의 조건을 만족하는 N개의 음이 아닌 정수를 출력한다.

각 정수는 10⁹보다 같거나 작아야 한다. 답이 여러 개인 경우 아무거나 출력한다.

 

반응형

풀이

---

import sys
input = sys.stdin.readline


N = int(input().rstrip())
array = [list(map(int, input().rstrip().split())) for _ in range(N)]
nums = [0 for _ in range(N)]

for i in range(N):
    for j in range(i,N):
        if array[i][j] == 0:
            continue
        nums[i] |= array[i][j]
        nums[j] |= array[i][j]

print(*nums)

 

728x90

입력에서 주어진 행렬은 수열 A를 기반으로 생성된 정사각행렬이다.

 

문제의 목표인 수열 A를 구하기 위해 주어진 정사각행렬을 통해 역추론 해보자.

 

정사각행렬에서 주 대각선에 해당하는 값은 읽을 수 없고 m_ij와 m_ji는 동일한 값을 가진다.

 

때문에 다음과 같이 반복문을 돌려준다.

 

for i in range(N):
    for j in range(i,N):

 

array[i][j] == A_i & A_j 이므로 A_i와 A_j는 nums[i] |= array[i][j], nums[j] |= array[i][j] 다음과 같이 구해 줄 수 있다.

 

(array는 행렬을 nums는 수열 A를 나타낸다.)

 

조금 풀어서 쉽게 설명해보자.

 

A_i 와 A_j 의 각 비트에서 공통으로 1의 값을 가지는 비트만 1의 값을 값을 가진다.

 

이는 array[i][j] 에서 1로 표현된 비트는 해당하는 수열값에서 항상 1을 가진다는 것으로 해석 할 수 있다.

 

(이해가 안 된다면 비트연산에 대한 개념을 찾아보는 것을 추천한다.)

 

이 과정을 반복하면 수열 A를 유추할 수 있다.

 

다만, 답은 여러가지가 있을 수 있다.

 

(함수를 미분하고 다시 적분했을 때 적분상수의 정확한 값을 알 수 없는 것과 같은 느낌이다.)

 

마지막으로 무의미한 연산과정을 줄이기 위해 행렬의 값이 0인 경우에는 과정을 생략하도록 한다.

 

(행렬의 값이 0 이라면 or 연산을 해도 같은 값이 나온다.)

 

---

import sys
input = sys.stdin.readline

N = int(input().rstrip())
for _ in range(N):
    print(max(list(map(int, input().rstrip().split()))), end=' ')

 

문제를 풀다 생각난 또 다른 풀이이다.

 

문제에서 요구하는 방식은 아니지만 해당 문제를 해결하는데 문제가 없다.

 

이렇게 쉽게 풀 수 있는 문제였다니...

 

기존 코드

또 다른 풀이

 

 

심지어 실행시간도 짧고 메모리도 적게 차지한다.