초이의 끄적끄적

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

# 16676 근우의 다이어리 꾸미기 (브론즈2)

• point. 그리디 알고리즘 -> 규칙성을 찾아라
• 0~10 => 1 / 11~110 => 2 / 111~1110 => 3 / 1111~11110 =>4 ~~
• ex) n = 88
• 입력받는 정수의 길이를 1로 표시
• n이 일의 자리 정수라면 1 
• n이 11보다 크거나 같다면 두 개의 스티커팩으로 표현 가능
• n이 11보다 작다면(10인 경우) 한 개의 스티커팩으로 표현 가능 

N= input()
S = '1'*len(N)

if len(N) == 1:
    print(1)
elif int(N) >= int(S):
    print(len(N))
else:
    print(len(N)-1)

# 2437 저울 (골드3)

• 무게가 양의 정수인 N개의 저울추가 주어질 때, 이 추들을 사용하여 측정할 수 없는 양의 정수 무게 중 최솟값을 구하는 프로그램을 작성하시오.
• 예를 들어, 무게가 각각 3, 1, 6, 2, 7, 30, 1인 7개의 저울추가 주어졌을 때, 이 추들로 측정할 수 없는 양의 정수 무게 중 최솟값은 21이다. 
• point. 그리디 알고리즘 -> 규칙성을 찾아라
• 현재까지의 합 + 1 보다 큰 값이 다음 인덱스에 저장된 수라면 이전의 추들로 무게를 구할 수 없다.

n, a = int(input()), sorted(list(map(int, input().split())))
ans = 0
for i in a:
    if i <= ans +1:
        ans += i
    else:
        break
print(ans+1)

단계별풀기 - 기본수학2

# 1002 터렛 (실버4)

• 조규현의 좌표 (x1, y1)와 백승환의 좌표 (x2, y2)가 주어지고, 조규현이 계산한 류재명과의 거리 r1과 백승환이 계산한 류재명과의 거리 r2가 주어졌을 때, 류재명이 있을 수 있는 좌표의 수를 출력하는 프로그램을 작성하시오.
• 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.
• point. 원과 원의 접점의 개수를 구하는 문제
  
  1. 두 원이 일치하는 경우 -> -1, 0
  2. 두 원이 한 점에서 만나는 경우(외접, 내접) -> 1
  3. 두 원이 만나지 않는 경우 -> 0
  4. 두 원이 두 점에서 만나는 경우 -> 2

t = int(input())
for i in range(t):
    x1, y1, r1, x2, y2, r2 = map(int, input().split())
    d = ((x2 - x1) ** 2 + (y2 - y1) ** 2) ** 0.5
    rs = r1 + r2
    rm = abs(r1 - r2)
    if d == 0:
        if r1 == r2:
            print(-1)
        else:
            print(0)
    else:
        if d == rs or d == rm:
            print(1)
        elif d < rs and d > rm:
            print(2)
        else:
            print(0)

단계별풀기 - 재귀

# 10872 팩토리얼 (브론즈 3)

• 0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

def fac(n):
    if n == 0:
        return 1
    elif n == 1:
        return 1
    return  n * fac(n-1)

N = int(input())
print(fac(N))

# 10870 피보나치수 5 (브론즈2)

• 첫째 줄에 n번째 피보나치 수를 출력한다.

def f(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    return  f(n-1) + f(n-2)

N = int(input())
print(f(N))