- 0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.
- 행렬을 변환하는 연산은 어떤 3*3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 -> 1, 1 -> 0)
- 첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
- point. A,B 행렬값을 비교해서 다르면 3*3 크기만큼 flip 시켜준다
N, M = map(int, input().split())
A = [list(map(int, list(input()))) for _ in range(N)]
B = [list(map(int, list(input()))) for _ in range(N)]
def flip(x,y,A):
for i in range(3):
for j in range(3):
A[x+i][y+j] ^= 1 # xor
ans = 0
for i in range(N-2):
for j in range(M-2):
if A[i][j] != B[i][j]:
flip(i,j,A)
ans +=1
if A != B:
print(-1)
else:
print(ans)
- K개의 소수가 주어졌을 때, 이러한 소수의 곱들 중에서 N번째 수를 구해 보자. 단 정답은 2**31보다 작은 자연수이다.
- point. 그리디 알고리즘 젤 어려운 문제, 네이버같은 곳에서 나옴
- heap 우선순위 큐를 사용하여 큐 안에 있는 값들 중 최소 값을 반환한다. (힙큐 최소힙 기반)
- 중복 처리 중요
import heapq
import copy
K,N = map(int, input().split())
p_list = list(map(int, input().split()))
lst, ck = copy.deepcopy(p_list), set() # ck 중복된 수를 포함하지 않기 위해
heapq.heapify(lst)
ith = 0
while ith < N :
mn = heapq.heappop(lst) # 꼭대기값
if mn in ck:
continue
ith += 1
ck.add(mn)
for i in p_list:
if mn*i < 2**32:
heapq.heappush(lst, mn*i)
print(mn)
단계별풀기 - 재귀
# 2447 별 찍기 -10(실버1)
def star(i):
global arr
idx = [ i for i in range(n) if (i//3**cnt_)%3 ==1]
for i in idx:
for j in idx:
arr[i][j] = " "
n = int(input())
v = n
cnt = 0
while v != 1:
v/=3
cnt +=1
arr = [["*"]*n for _ in range(n)]
for cnt_ in range(cnt):
star(cnt_)
print('\n'.join([''.join([str(i) for i in row]) for row in arr]))
# 11729 하노이 탑 이동 순서 (실버2)
- 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
- 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
- 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
- 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
- point. 하노이탑 이동 규칙. n개의 원판이 있을 때, n-1개의 원판 즉, 맨 밑의 원판을 제외하고 나머지 원판들을 1번에서 2번으로 옮긴 뒤, 맨 밑의 원판을 1번에서 3번으로 옮긴다. 그리고 n-1개의 원판들을 다시 2번에서 3번으로 옮긴다.
def hanoi(disk, start, mid, end):
if disk == 1:
print(start, end)
else:
hanoi(disk - 1, start, end, mid) # 목적지가 아닌 곳으로 재귀적으로 이동
print(start, end)
hanoi(disk - 1, mid, start, end) # 다른 곳으로 옮겼던 원반들을 그 위에 얹는다
total_disk = int(input())
total_mvmt = 0
for disk in range(total_disk):
total_mvmt = total_mvmt * 2
total_mvmt += 1
print(total_mvmt)
hanoi(total_disk, 1, 2, 3)반응형
'알고리즘 > baekjoon' 카테고리의 다른 글
| 20210129_코테공부 (0) | 2021.01.29 |
|---|---|
| 20210128_코테공부 (0) | 2021.01.28 |
| 20210126_코테공부 (0) | 2021.01.26 |
| 20210125_코테공부 (0) | 2021.01.25 |
| 20210122_코테공부 (0) | 2021.01.22 |
