20210127_코테공부

# 1080 행렬 (실버 2)

• 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)

 

# 2014 소수의 곱 (골드2)

• 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개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 옮기려 한다.
  1. 한 번에 한 개의 원판만을 다른 탑으로 옮길 수 있다.
  2. 쌓아 놓은 원판은 항상 위의 것이 아래의 것보다 작아야 한다.
• 이 작업을 수행하는데 필요한 이동 순서를 출력하는 프로그램을 작성하라. 단, 이동 횟수는 최소가 되어야 한다.
• 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)