[백준][파이썬] 23080번 - 스키테일 암호

문제 번호 : 23080번 - 스키테일 암호
문제 출처 : https://www.acmicpc.net/problem/23080

Code

k = int(input())
s = input()

answer = ''
for i in range(0, len(s), k):
    answer += s[i]

print(answer)

Idea

막대 둘레에 따라서 문자열을 출력하면 되는 간단한 문제이다.

s\[k\*0\], s\[k\*1\], s\[k\*2\], ... 순으로 출력하면 되기 때문에 range(시작, 끝, 간격) 을 이용해서 k마다 문자를 출력했다.

[백준][파이썬] 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등이었는데 글 적을 때 되니까 밀려났다.

[백준][파이썬] 2210번 - 숫자판 점프

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

Code

import sys


def recursive(x, y, count):
    if count == 5:
        number.append(numbers[x][y])
        answer_set.add(tuple(number))
    else:
        number.append(numbers[x][y])
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if -1 < nx < 5 and -1 < ny < 5:
                recursive(nx, ny, count + 1)
    number.pop()

numbers = [sys.stdin.readline().split() for _ in range(5)]

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

answer_set = set()
number = []
for r in range(5):
    for c in range(5):
        recursive(r, c, 0)

print(len(answer_set))

Idea

1. 각각의 시작점에서 가능한 방향으로 모두 방문하며 list에 숫자를 추가
2. 숫자 리스트를 집합 자료형에 입력함으로써 중복을 제거
3. 재귀함수가 호출 되고나서 입력받은 리스트와 같은 새로운 리스트를 만들지 않고 기존의 리스트를 append와 pop을 사용해서 스택으로 사용

집합의 요소로는 리스트가 들어갈 수 없다. 그래서 집합에 add를 할 때 리스트를 tuple이나 str로 변환하여 입력해주어야 했다. 집합은 직접 수정이 불가능한 자료형인데 리스트는 주소에 의한 수정이 가능해져서가 아닐까 추측해본다.