척척석사의 코딩기록

문제는 다음과 같습니다.

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

Typical한 구현 문제였고, 케이스를 잘 나누어주면서 풀어주면 되겠습니다.

이러한 문제들의 경우, 몇가지 특이한 케이스가 어디로 이동하게 되는지 체크하면, 규칙성이 눈에 보이기 쉬운 문제 같습니다.

해답 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

N, M, R = map(int,input().split())
mat = []
for _ in range (0,N):
    a = list(map(int,input().split()))
    mat.append(a)
def oper(k,mat):
    column = len(mat)
    row = len(mat[0])
    if k == 1: #상하반전
        new_mat = []
        for i in range (column-1,-1,-1):
            new_mat.append(mat[i])

    elif k == 2: #좌우반전
        new_mat = []
        for i in range (0,column):
            new_col = []
            for j in range (row-1,-1,-1):
                new_col.append(mat[i][j])
            new_mat.append(new_col)

    elif k == 3: #오른쪽으로 90도 회전
        new_mat = [[0 for _ in range (0,column)] for _ in range (0,row)]
        for i in range (0,column):
            for j in range (0,row):
                new_mat[j][column-1-i] = mat[i][j]

    elif k == 4: #왼쪽으로 90도 회전
        new_mat = [[0 for _ in range(0, column)] for _ in range(0, row)]
        for i in range (0,column):
            for j in range (0,row):
                new_mat[row-1-j][i] = mat[i][j]

    elif k == 5 or k == 6: #4개로 나눈 뒤에 시계방향 회전
        n = column // 2
        m = row // 2
        new_mat = [[0 for _ in range (0,row)] for _ in range (0,column)]
        block_1, block_2, block_3, block_4 = [],[],[],[]
        for i in range (0,n):
            t = []
            for j in range (0,m):
                t.append(mat[i][j])
            block_1.append(t)

        for i in range (0,n):
            t = []
            for j in range (m,row):
                t.append(mat[i][j])
            block_2.append(t)

        for i in range (n,column):
            t = []
            for j in range (0,m):
                t.append(mat[i][j])
            block_4.append(t)

        for i in range (n,column):
            t = []
            for j in range (m,row):
                t.append(mat[i][j])
            block_3.append(t)

        #분할
        if k == 5:
            for i in range (0,column):
                for j in range (0,row):
                    if 0 <= i < n and 0 <= j < m:
                        new_mat[i][j] = block_4[i][j]
                    elif 0 <= i < n and m <= j < row:
                        new_mat[i][j] = block_1[i][j-m]
                    elif n <= i < column and m <= j < row:
                        new_mat[i][j] = block_2[i-n][j-m]
                    elif n <= i < column and 0 <= j < m:
                        new_mat[i][j] = block_3[i-n][j]

        elif k == 6:
            for i in range (0,column):
                for j in range (0,row):
                    if 0 <= i < n and 0 <= j < m:
                        new_mat[i][j] = block_2[i][j]
                    elif 0 <= i < n and m <= j < row:
                        new_mat[i][j] = block_3[i][j-m]
                    elif n <= i < column and m <= j < row:
                        new_mat[i][j] = block_4[i-n][j-m]
                    elif n <= i < column and 0 <= j < m:
                        new_mat[i][j] = block_1[i-n][j]
    return new_mat

cmd = list(map(int,input().split()))
for i in range (0,R):
    mat = oper(cmd[i],mat)

for i in range (0,len(mat)):
    print(*mat[i])

일본에 다녀오고, 여러가지 생각을 정리하면서 간만에 올리는 포스팅이 되겠습니다.

문제는 다음과 같습니다.

즉, 이전에 지나오지 않았던 발판으로 얼만큼 늘어날 수 있는가? 라는 문제가 되겠습니다.

백트래킹의 교과서 같은 문제 중 하나인 것 같습니다.

시간이 좀 여유로울 것 같아서 여러가지 오답 코드를 작성했습니다만 (이전에 방문했던 포인트들을 리스트로 만들어서 하나하나 체크한다던지)

결국 등장한 알파벳을 True로 세팅하고, 아닌 경우에는 False로 체크하는 방식으로 진행하는것이 제일 좋아보였습니다.

코드는 다음과 같이 나오겠습니다.

R,C = map(int,input().split())
mapp = []
for _ in range (0,R):
    a = input()
    mapp.append(a)

moving = [(0,1),(-1,0),(1,0),(0,-1)]
ans = 0
visited = [False for _ in range (0,26)]
visited[ord(mapp[0][0]) - 65] = True
cnt = 1
def bfs(n,m):
    global ans
    global visited
    global cnt
    ans = max(ans, cnt)
    for k in range (0,4):
        nn,mm = n + moving[k][0], m + moving[k][1]
        if 0 <= nn < R and 0 <= mm < C and visited[ord(mapp[nn][mm]) - 65] == False:
            visited[ord(mapp[nn][mm])-65] = True
            cnt += 1
            bfs(nn,mm)
            visited[ord(mapp[nn][mm])-65] = False
            cnt -= 1
bfs(0,0)
print(ans)

즉, 제한된 금액을 기반으로 최대의 숫자를 만들어내는 프로그램을 작성하는 것이 되겠다.

스펙은 다음과 같습니다.

파이썬에서는 그래도 나름 괜찮은 퍼포먼스였던 것 같다. 메모리를 더 줄일 수 있다면 좋을 것 같다.

그리고 작성한 프로그램은 다음과 같다.

N = int(input())
value = list(map(int,input().split()))
M = int(input())

dp = [-1 for _ in range (0, 51)]

for i in range (0,N):
    if M - value[i] >= 0:
        dp[M-value[i]] = max(dp[M-value[i]], i)

for i in range (50,-1,-1):
    if dp[i] != -1:
        main_number = str(dp[i])
        for j in range (0,N):
            if i - value[j] >= 0:
                new_number = main_number + str(j)
                dp[i - value[j]] = max(dp[i - value[j]], int(new_number))

ans = max(dp)
print(ans)

이 방법은 냅색 문제와 비슷한 느낌으로 풀었던 것 같다.

dp라는 array를 만들어 둔 뒤, 각각의 index가 "보유한 돈"을 나타낸다고 생각하자.

그리고 dp[index]는 보유한 돈을 바탕으로 가장 큰 수를 나타낸다고 하자.

첫번째 반복문에서 "한자릿수"의 카드들을 먼저 배치하는 상황이 되겠다.

두번째 반복문은, 50 -> 0 순으로 가지고 있는 돈이 적어지는 순으로 반복이 진행된다고 생각하면 좋을 것 같다.

무엇인가를 사는 이상 보유한 돈은 반드시 줄어들기 때문이다.  (마치 monotonically decreasing 같다)

main_number는 보유한 돈이 i일때 나타낼 수 있는 최대 숫자를 나타내고,

new_number는 이 최대 숫자 뒤에 어떤 숫자를 붙일 수 있을지 판단하면서 i - value[j]의 값과 대소를 비교하게 되겠다.

그리고 마지막으로 dp값에서 가장 큰 것을 찾아주면 되겠다.

원래 문제는 다음과 같습니다.

생각보다 순서대로 분기를 잘 나눠주면서 하면 될 것 같습니다.

from collections import defaultdict
import sys
import heapq
input = sys.stdin.readline

score_dae, score_gyu = 0,0
num_dae, num_gyu = defaultdict(int), defaultdict(int)
third_prime_dae, third_prime_gyu = [-1,-1,-1], [-1,-1,-1]


prime = defaultdict(int)
num = [False for _ in range (0,5000001)]
num[0], num[1] = True, True
for i in range (2,5000001):
    if num[i] == False:
        prime[i] = 1
        for j in range (2 * i, 5000001, i):
            num[j] = True
#prime에 소수 저장 완료

def check(n,i):
    global third_prime_gyu
    global third_prime_dae
    global score_gyu
    global score_dae
    if prime[n] == 0: #소수가 아닌 경우 페널티를 주는 방향으로
        if i == -1: #-1를 대웅이의 턴
            x = heapq.heappop(third_prime_gyu)
            if x == -1:
                score_gyu += 1000
                heapq.heappush(third_prime_gyu, -1)
            else:
                score_gyu += x
                heapq.heappush(third_prime_gyu, x)
        elif i == 1: #1을 규성이의 턴
            x = heapq.heappop(third_prime_dae)
            if x == -1:
                score_dae += 1000
                heapq.heappush(third_prime_dae, -1)
            else:
                score_dae += x
                heapq.heappush(third_prime_dae, x)
    else: #일단 소수를 말했는가?
        if num_dae[n] != 0 or num_gyu[n] != 0: #이전에 말해진 소수인 경우
            if i == -1:
                score_dae -= 1000
            elif i == 1:
                score_gyu -= 1000
        elif num_dae[n] == 0 and num_gyu[n] == 0: #이전에 나오지 않은 수
            if i == -1:
                num_dae[n] = 1
                heapq.heappush(third_prime_dae,n)
                heapq.heappop(third_prime_dae)
            elif i == 1:
                num_gyu[n] = 1
                heapq.heappush(third_prime_gyu, n)
                heapq.heappop(third_prime_gyu)
N = int(input())
for _ in range (0,N):
    a,b = map(int,input().split())
    check(a,-1)
    check(b,1)

if score_dae > score_gyu:
    print("소수의 신 갓대웅")
elif score_dae < score_gyu:
    print("소수 마스터 갓규성")
elif score_dae == score_gyu:
    print("우열을 가릴 수 없음")

1이상 백만 이하의 어떤 수가 주어졌을 때, 해당하는 수를 4개의 소수의 합으로 나타내는 문제가 되겠다.

여기서 한가지 알아두면 좋은 것이 골드바흐의 추측이다.

https://ko.wikipedia.org/wiki/%EA%B3%A8%ED%8A%B8%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%94%EC%B8%A1

여기에서 수치적인 분석에 의하면 $10^{18}$ 까지는 해당 추측이 성립한다고 한다 !

-> 백만정도는 이 수치 안에 포함되므로 어렵지 않다는 것을 알 수 있겠다.

즉, 케이스를 나눠본다면 다음과 같이 나눌 수 있겠다.

1. 주어진 수 N이 홀수 / 짝수 인가?

2.1 $N$이 홀수인 경우

짝수인 소수는 2 하나뿐이므로, 다음과 같이 케이스를 나눌 수 있겠다.

2.1.1 4개의 숫자 중 2가 1개 존재하는 경우. $(2,x,y,z)$

그렇다면 $ N-2$는 3이상의 세개의 소수의 합으로 나타내어지는가? 

계산의 편의를 위해, 이때는 세개 중 하나의 소수가 3이라고 해버리자.

그렇다면 $N-5$ 가 4이상인 짝수 일 때, 골드바흐의 추측을 인정한다면 나타낼 수 있다는 것이므로 소수의 집합을 반복문을 돌면서

$N-5 = p1 + p2$ ($p1,p2$ 는 소수)인지 확인해주면 되겠다.

2.1.2 4개의 숫자 중 2가 3개 존재하는 경우. $(2,2,2, x)$

$N-6$이 소수인지 확인하면 되겠다.

2.2 주어진 수가 짝수인 경우

마찬가지 짝수인 소수는 2만 존재하므로 다음과 같이 케이스를 나누자.

2.2.1. 4개의 숫자 중 2가 4개 존재하는 경우. $(2,2,2,2)$

즉, $N$이 8인지 체크

2.2.2. 4개의 숫자 중 2가 2개 존재하는 경우. $(2,2,x,y)$

$N-4$에 대해서 반복문을 순환해주면 되겠다. (2.1.1과 유사한 방법)

소스 코드는 다음과 같이 나온다.

import math
from collections import defaultdict
N = int(input())
def prime(n):

    num = [False for _ in range (0,n+1)]
    num[0] , num[1] = True, True
    m = int(math.sqrt(n) + 1)
    prime_number = []
    prime_num = defaultdict(int)
    for i in range (2, n+1):
        if num[i] == False and i != 2:
            prime_number.append(i)
            prime_num[i] += 1
            for j in range (i,n+1,i):
                num[j] = True
    #4이상의 짝수는 두 홀수인 소수의 합으로 나타낼 수 있다 -> Goldbach's conjecture

    #prime_number는 3이상의 소수들의 집합
    if n % 2 == 0:
        if n == 8:
            return [2,2,2,2]
        elif n - 4 >= 6: #3이상의 소수 2개의 합으로 이루어진 경우
            for x in prime_number:
                if prime_num[n-4-x] != 0:
                    return [2,2,x,n-4-x]

    elif n % 2 != 0:
        # 2가 3개 존재하고, 3이상의 소수가 1개 존재하는 경우
        if n - 6 in prime_number:
            return [2,2,2,n-6]
        else:
            #n-5를 2개의 소수의 합으로 나타내야하는 상황
            for x in prime_number:
                if prime_num[n-5-x] != 0:
                    return [2,3,x,n-5-x]
    return [-1]

print(*prime(N))

from collections import defaultdict
import math
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))

div1, div2 = defaultdict(int), defaultdict(int)
#A를 위한것
def a(n):
    t = int(math.sqrt(n)) + 1
    for i in range (2,t):
        if n % i == 0:
            while n % i == 0:
                div1[i] += 1
                n //= i
    if n != 1:
        div1[n] += 1
    return

def b(n):
    t = int(math.sqrt(n)) + 1
    for i in range(2, t):
        if n % i == 0:
            while n % i == 0:
                div2[i] += 1
                n //= i
    if n != 1:
        div2[n] += 1
    return

for aa in A:
    a(aa)
for bb in B:
    b(bb)


num = list(div1.keys())
ans = 1

check = False
for x in num:
    if x in div2:
        ans *= (x ** min(div1[x], div2[x]))
        if ans >= 1_000_000_000:
            check = True
            ans %= 1_000_000_000
if check == True:
    y = len(str(ans))
    ans = "0" * (9-y) + str(ans)
    print(ans)
else:
    print(ans)

곱해져서 A와 B가 된다는 것은 본질적인 질문은 아니라고 생각되는 문제였다. 

(괜히 말이 더 어렵게 느껴지는 여지가 있을듯?)

A와 B라는 리스트가 주어져 있을 때, 각 요소들을 소인수분해 한 뒤에 최대공약수를 구하는 방침으로 구하면 되겠다.

결국 아이디어는 어렵지는 않은 문제인 것 같다.

A = x_1^{y_1} * x_2^{y_2} * ... * x_n^{y_n},  B = x_1^{z_1} * x_2^{z_2}* ... * x_n^{z_n}  (Each x_i is prime number)

이런 꼴로 주어져 있을때, A와 B의 최대공약수는

gcd(A,B) = x_1^{min(y_1, z_1)} * x_2^{min(y_2, z_2)} * ... * x_n^{min(y_n,z_n)} 이런 꼴로 나타내어진다는 것에 유의 !

사실, 공통인 소인수를 갖지 않는 경우에도 동일한 논리를 적용할 수 있다. ㅎㅎ.

간단한 일차방정식의 꼴을 준 뒤, 초기값의 궤도가 그 이후와 일치하는가? 라는 것을 물어보는 문제가 되겠다.

즉, 어떤 함수 f(x) = ax + b가 주어져있을 때

초기값을 x_0 이라고 하고, i+1번째 항을 x_i로 둔다면

x_i = f(x_{i-1}) = f(f(x_{i-2})) = .... = f .... f(x_0) 꼴인가? 라는 것을 묻는 문제가 되겠습니다.

그리고 이에 해당하는 코드는 아래와 같습니다.

N = int(input())
num = list(map(int,input().split()))

def f(num):
    if len(num) == 1:
        return "A"
    else:
        ans = []
        for a in range (-200,201):
            b = num[1] - (a * num[0])
            jud = True
            for i in range (1, N):
                if a * num[i-1] + b != num[i]:
                    jud = False
                    break
            if jud == True:
                ans.append(a * num[-1] + b)
        ans = list(set(ans))
        if len(ans) == 1:
            return ans[0]
        elif len(ans) > 1:
            return "A"
        elif len(ans) == 0:
            return "B"
print(f(num))

2개의 누적합을 얼마나 잘 쓸 수 있겠니? 라는 문제인데

사실 누적합과 딕셔너리만 있어도 풀 수 있는 문제 같다

(키워드에는 이분 탐색이 있길래...)

물론, 이분 탐색을 통해서 빠르게 값을 찾아내는 것도 중요하겠다.

대신 이 경우에는 딕셔너리가 아닌 값을 사용해야겠지만 ...

답안 코드는 아래와 같다

from collections import defaultdict
T = int(input())
N = int(input())
A = list(map(int,input().split()))
M = int(input())
B = list(map(int,input().split()))


psum_A = [0 for _ in range (0,N+1)]
psum_B = [0 for _ in range (0,M+1)]
for i in range (1,N+1):
    psum_A[i] = psum_A[i-1] + A[i-1]
for i in range (1,M+1):
    psum_B[i] = psum_B[i-1] + B[i-1]

partial_sum_A = defaultdict(int)
partial_sum_B = defaultdict(int)

for i in range (1, N+1):
    for j in range (0,i):
        partial_sum_A[psum_A[i] - psum_A[j]] += 1

for i in range (1, M+1):
    for j in range (0,i):
        partial_sum_B[psum_B[i] - psum_B[j]] += 1

pnum_A = list(partial_sum_A.keys())
pnum_A.sort()
cnt = 0

for i in range (0,len(pnum_A)):
    target = T - pnum_A[i]
    if target in partial_sum_B:
        cnt += partial_sum_A[pnum_A[i]] * partial_sum_B[target]
print(cnt)