[백준][파이썬] 17406번 - 배열 돌리기 4

문제 번호 : 17406번 - 배열 돌리기 4
문제 출처 : https://www.acmicpc.net/problem/17406

Code

from itertools import permutations

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
val = []


def matrix_value(ans):
    for i in range(n):
        ans = min(ans, sum(matrix[i]))
    return ans


def rotate(rcs):
    r, c, s = rcs
    for i in range(1, s+1):
        tmp = matrix[r - 1 - i][c - 1 - i]
        x = r - i - 1
        y = c - i - 1
        for j in range(4):
            for k in range(2*i):
                nx = x + dx[j]
                ny = y + dy[j]
                matrix[x][y] = matrix[nx][ny]
                x, y = nx, ny
        matrix[r-1-i][c-i] = tmp


n, m, k = map(int, input().split())
a = [[] for _ in range(n)]
for h in range(n):
    a[h] = list(map(int, input().split()))
rotation = [[] for _ in range(k)]
for i in range(k):
    rotation[i] = list(map(int, input().split()))
answer = 1e9
orders = permutations(rotation)

for order in orders:
    matrix = [a[row][:] for row in range(n)]
    for rcs in order:
        rotate(rcs)
    answer = matrix_value(answer)

print(answer)

Idea

1. 회전하는 경우의 수를 순열을 통해서 구한다. K의 최대값이 6이기 때문에 6! = 720개의 경우가 만들어진다.
2. 각 경우의 수마다 배열을 복사하고 회전을 시킨 후 각 행마다 최솟값인지 확인한다.

[백준][파이썬] 17089 - 세 친구

문제 번호 : 17089번 세 친구
문제 출처 : https://www.acmicpc.net/problem/17089

Code

import sys

n, m = map(int, input().split())
relations = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]

friends = [set() for _ in range(n)]
for relation in relations:
    friends[relation[0]-1].add(relation[1])
    friends[relation[1]-1].add(relation[0])

num_friends = m
for a in range(n):
    for b in friends[a]:
        for c in friends[b-1]:
            if c in friends[a]:
                num_friends = min(num_friends, len(friends[a]) + len(friends[b-1]) + len(friends[c-1]) - 6)
if num_friends < m:                
    print(num_friends)
else:
    print(-1)

Idea

1. 입력된 친구가 모두 A, B, C의 친구인 경우 세 친구의 친구 수 합의 최대는 m - 6이다.
2. A를 정하고 B는 A의 친구 중 한명이고 C는 B의 친구이면서 A의 친구인 경우에서 친구 수의 최소값을 찾아낸다.
3. b > a, c > b 조건을 넣은 이유는 먼저 순회한 조합을 순회하지 않기 위함이다. 이 두 조건이 없다면 순열처럼 동작할 것이지만 이 조건으로 인해서 조합이 되어서 시간 복잡도가 줄어든다. 이 조건 두 줄만으로 1880ms에서 92ms로 시간이 확 줄었다.

[백준][파이썬] 2422번 - 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

문제 번호 : 2422
문제 출처 : https://www.acmicpc.net/problem/2422

Code

import sys

n, m = map(int, input().split())
answer = n * (n - 1) * (n - 2) // 6
nomat = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, sys.stdin.readline().split())
    answer -= (n-2) - len(nomat[a-1] | nomat[b-1])
    nomat[a-1].add(b)
    nomat[b-1].add(a)

print(answer)

Idea

1. 초기 answer 값은 \( {}_n \mathrm {C}_3 \) 을 수로 나타낸 것이다.
2. nomat 리스트에는 각 맛 별로 조합이 좋지 않은 맛을 넣는다.
3. 2 가지가 정해진 상황에서 나머지 한 가지 맛을 고르는 경우의 수는 n - 2 이다.
4. 그 전에 경우의 수에서 없앤 경우의 수는 합집합의 길이가 된다.

예제 입력을 넣었을 때를 예시로 들면 다음과 같다.

    1. 모든 경우의 수는 5가지 맛 중 3가지를 뽑는 경우로 총 10이다.  
    2. 처음 (1, 2, X) 를 뽑는 경우의 수는 3가지이므로 전체 경우의 수에서 3을 빼준다.  
    3. (3, 4, X) 를 뽑는 경우의 수 중 전에 뽑은 경우가 없으므로 `nomat\[2\]`와 `nomat\[3\]`의 합집합의 길이는 0이다.  
    4. (1, 3, X) 를 뽑는 경우에는 (1, 2, 3) 인 경우와 (1, 3, 4) 인 경우를 그 전의 입력에서 뺐으므로 전체 경우의 수에서 1만 빼준다.

처음에 코드 제출했을 때는 파이썬 언어에서 시간 순위 1등이었는데 글 적을 때 되니까 밀려났다.

[백준][파이썬] 16936번 - 나3곱2

문제 번호 : 16936

문제 출처 : https://www.acmicpc.net/problem/16936

Code

n = int(input())
B = list(map(int, input().split()))
x = min(B)
old_power = 0

for b in B:
    i = 3
    power = 0
    while i <= b:
        if b % i == 0:
            power += 1
        i *= 3
    if power > old_power or (power == old_power and b < x):
        x = b
        old_power = power
        
A = []
A.append(x)
count = 1
while count < n:
    if x * 2 in B:
        x = x * 2
        A.append(x)
        count += 1
    else:
        x = x // 3
        A.append(x)
        count += 1

for a in A:
    print(a, end=' ')

Idea

1. 가장 큰 수가 짝수이면 얘는 절대 x는 아니다?    False
   
   • 예제 2번에서 보듯 가장 큰 수가 짝수여도 x일 수 있다.
2. 오른쪽으로 갈수록 수의 2^n배 증가하고 3^-n배로 감소한다.
3. 3의 n승을 약수로 가질 때 n이 클수록 왼쪽에 위치한다.
4. 같은 지수를 가지는 수 중에서 가장 작은 수가 x가 된다.
5. x를 시작으로 법칙대로 수를 A 리스트에 삽입한다.

처음에 생각할 때에는 한 노드에서 2 가지를 모두 탐색한 후 다시 되돌아와서 다른 방향으로 가야 될거라 생각했다.

다른 사람들의 풀이에는 재귀함수를 사용한 경우도 많아 보였다. 나는 x를 찾은 후 문제의 알고리즘대로 A 수열을 만들었는데 다른 사람의 코드에서는 이차원 리스트와 lambda를 사용해서 정렬을 하기도 했다.

n = int(input())
b = list(map(int, input().split()))

a = []

for num in b:
    can3 = 0
    num_origin = num
    while True:
        if num % 3 == 0:
            can3 += 1
            num //= 3
        else:
            break
    a.append([can3, num_origin])

a.sort(key= lambda x: (-x[0], x[1]))
for i in range(n):
    print(a[i][1], end=' ')

이 코드가 훨씬 간결해보인다. key = lambda x: (-x[0], x[1])로 정렬한 것은 -x[0] 즉 3으로 나누어지는 수가 큰 것으로 정렬한 후 원래 값이 작은 순으로 정렬한다. 정렬의 기본 순서는 오름차순이므로 -x[0]를 기준으로 하면 큰 수가 앞으로 온다.

반복문을 진행하면서 모든 과정을 끝내는 것을 연습해야 된다고 생각이 들었다.