졍's 기술 블로그

행렬

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그리디 알고리즘

문제

0과 1로만 이루어진 행렬 A와 행렬 B가 있다. 이때, 행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하시오.

행렬을 변환하는 연산은 어떤 3×3크기의 부분 행렬에 있는 모든 원소를 뒤집는 것이다. (0 → 1, 1 → 0)

입력

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

출력

첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.

예제 입출력

Algorithm

구현 - Simulation
1. 다른 숫자인 곳을 왼쪽 위 지점으로 잡고 연산
2. 모두 변환 후 A와 B가 동일한지 비교

Code

# [x][y]의 위치의 값이 같은지 다른지 확인
def is_same(x, y):
    if A[x][y] != B[x][y]:
        return False
    else:
        return True

# [x][y]의 위치의 값을 변경
def change(x, y):
    # [x][y]부터 3x3이 범위를 벗어나면 for문 들어가지 않음
    if x+3 > N or y+3 > M:
        return False
    
    for xx in range(x, x+3):
        for yy in range(y, y+3):
            # 0이면 1로 변경
            if A[xx][yy] == 0:
                A[xx][yy] = 1
            else:
                A[xx][yy] = 0
    return True

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
A = [list(map(int, input().rstrip())) for _ in range(N)]
B = [list(map(int, input().rstrip())) for _ in range(N)]

answer = 0
for x in range(N):
    for y in range(M):
        # 다른 숫자인 곳이 있으면
        if not is_same(x, y):
            # 해당 위치부터 3x3 만큼 연산
            if change(x, y):
                answer += 1

# A와 B가 같으면 answer 출력
if A==B:
    print(answer)
# 같지 않으면 -1 출력
else:
    print(-1)

메모리: 30840 KB
시간: 76 ms

카드 합체 놀이

티어 : Silver 1
시간 제한 : 1 초 (추가 시간 없음)
메모리 제한 : 512 MB
알고리즘 분류 : 자료 구조, 그리디 알고리즘, 우선순위 큐

문제

석환이는 아기다. 아기 석환이는 자연수가 쓰여져있는 카드를 갖고 다양한 놀이를 하며 노는 것을 좋아한다. 오늘 아기 석환이는 무슨 놀이를 하고 있을까? 바로 카드 합체 놀이이다!

아기 석환이는 자연수가 쓰여진 카드를 n장 갖고 있다. 처음에 i번 카드엔 ai가 쓰여있다. 카드 합체 놀이는 이 카드들을 합체하며 노는 놀이이다. 카드 합체는 다음과 같은 과정으로 이루어진다.

1. x번 카드와 y번 카드를 골라 그 두 장에 쓰여진 수를 더한 값을 계산한다. (x ≠ y)
2. 계산한 값을 x번 카드와 y번 카드 두 장 모두에 덮어 쓴다.

이 카드 합체를 총 m번 하면 놀이가 끝난다. m번의 합체를 모두 끝낸 뒤, n장의 카드에 쓰여있는 수를 모두 더한 값이 이 놀이의 점수가 된다. 이 점수를 가장 작게 만드는 것이 놀이의 목표이다.

아기 석환이는 수학을 좋아하긴 하지만, 아직 아기이기 때문에 점수를 얼마나 작게 만들 수 있는지를 알 수는 없었다(어른 석환이는 당연히 쉽게 알 수 있다). 그래서 문제 해결 능력이 뛰어난 여러분에게 도움을 요청했다. 만들 수 있는 가장 작은 점수를 계산하는 프로그램을 만들어보자.

입력

첫 번째 줄에 카드의 개수를 나타내는 수 n(2 ≤ n ≤ 1,000)과 카드 합체를 몇 번 하는지를 나타내는 수 m(0 ≤ m ≤ 15×n)이 주어진다.

두 번째 줄에 맨 처음 카드의 상태를 나타내는 n개의 자연수 a1, a2, …, an이 공백으로 구분되어 주어진다. (1 ≤ ai ≤ 1,000,000)

출력

첫 번째 줄에 만들 수 있는 가장 작은 점수를 출력한다.

예제 입출력

Algorithm

구현
1. 숫자 오름차순
2. 가장 맨 앞 두 숫자 더한 값으로 대체
3. 1과 2를 m번 반복

Code

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cards = list(map(int, input().split()))

for count in range(m):
    # 숫자 오름차순
    cards.sort()
    cards[0], cards[1] = cards[0]+cards[1], cards[0]+cards[1]

print(sum(cards))

메모리: 30840 KB
시간: 240 ms

A→B

티어 : Silver 1
시간 제한 : 2 초
메모리 제한 : 512 MB
알고리즘 분류 : 그래프 이론, 그리디 알고리즘, 그래프 탐색, 너비 우선 탐색

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (

)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입출력

Algorithm

Greedy
1. B가 2로 나누어 떨어지면 2로 나누기
2. 그렇지 않고 마지막 숫자가 1이면 1 빼기
3. 마지막 숫자가 1이 아니면 -1 출력
4. A가 만들어지면 횟수 출력
5. A보다 작아지면 -1 출력

Code

A, B = map(int, input().split())
answer = 0
while True:
    # B가 2로 나누어 떨어지면 2로 나누기
    if B % 2 == 0:
        B //= 2
        answer += 1
    # B가 2로 나누어 떨어지지 않고 마지막 숫자가 1이면 1 빼기
    elif str(B)[-1] == '1':
        B = int(str(B)[:-1])
        answer += 1
    # B가 2로 나누어 떨어지지 않고 마지막 숫자가 1이 아니면 -1 출력
    else:
        print(-1)
        break
    
    # B가 A보다 작아지면 -1 출력
    if A > B:
        print(-1)
        break
    # A가 만들어지면 횟수 출력
    elif A == B:
        print(answer+1)
        break

메모리: 30840 KB
시간: 72 ms

보물

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 :128  MB
알고리즘 분류 : 수학, 그리디 알고리즘, 정렬

문제

옛날 옛적에 수학이 항상 큰 골칫거리였던 나라가 있었다. 이 나라의 국왕 김지민은 다음과 같은 문제를 내고 큰 상금을 걸었다.

길이가 N인 정수 배열 A와 B가 있다. 다음과 같이 함수 S를 정의하자.

S = A[0] × B[0] + ... + A[N-1] × B[N-1]

S의 값을 가장 작게 만들기 위해 A의 수를 재배열하자. 단, B에 있는 수는 재배열하면 안 된다.

S의 최솟값을 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 A에 있는 N개의 수가 순서대로 주어지고, 셋째 줄에는 B에 있는 수가 순서대로 주어진다. N은 50보다 작거나 같은 자연수이고, A와 B의 각 원소는 100보다 작거나 같은 음이 아닌 정수이다.

출력

첫째 줄에 S의 최솟값을 출력한다.

예제 입출력

Algorithm

정렬
1. A 배열 오름차순 정렬
2. B 배열 내림차순 정렬
3. S = {A의 최솟값 * B의 최댓값}의 합

Code

N = int(input())
A = [int(num) for num in input().split()]
B = [int(num) for num in input().split()]

# A 배열 오름차순, B 배열 내림차순
A.sort()
B.sort(reverse=True)

# S = A최솟값 * B최댓값
S = 0
for idx in range(N):
    S += A[idx] * B[idx]
    
print(S)

메모리: 30840 KB
시간: 72 ms

로프

티어 : Silver 4
시간 제한 : 2 초
메모리 제한 : 192 MB
알고리즘 분류 : 수학, 그리디 알고리즘, 정렬

문제

N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다.

하지만 여러 개의 로프를 병렬로 연결하면 각각의 로프에 걸리는 중량을 나눌 수 있다. k개의 로프를 사용하여 중량이 w인 물체를 들어올릴 때, 각각의 로프에는 모두 고르게 w/k 만큼의 중량이 걸리게 된다.

각 로프들에 대한 정보가 주어졌을 때, 이 로프들을 이용하여 들어올릴 수 있는 물체의 최대 중량을 구해내는 프로그램을 작성하시오. 모든 로프를 사용해야 할 필요는 없으며, 임의로 몇 개의 로프를 골라서 사용해도 된다.

입력

첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.

출력

첫째 줄에 답을 출력한다.

예제 입출력

Algorithm

Greedy 이용
1. 각 로프의 중량을 리스트에 담아 sort
2. 1개 쓸 때부터 N개 쓸 때까지의 최댓값 구하기
    ☞ 각 최댓값은 [N-i] * i

Code

import sys
input = sys.stdin.readline

# 입력
N = int(input())
weights = []
for _ in range(N):
    weights.append(int(input()))

# 중량 리스트 오름차순 정렬
weights.sort()

# 로프 i개 쓸 때부터 N개 쓸 때까지 최댓값 갱신
max_weights = 0
for i in range(1, N+1):
    if max_weights < weights[N-i] * i:
        max_weights = weights[N-i] * i
print(max_weights)

메모리: 34080 KB
시간: 140 ms

회의실 배정

티어 : Silver 2
시간 제한 : 2 초
메모리 제한 : 128 MB
알고리즘 분류 : 그리디 알고리즘, 정렬

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은

보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

예제 입출력

힌트

(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.

Algorithm

Greedy
1. 리스트로 입력받아 끝나는 시간을 기준으로 오름차순 정렬
2. stack에 첫 번째 회의 추가
3. stack의 마지막 회의의 끝나는 시간보다 시작 시간이 크거나 같은 회의만 추가
4. stack의 길이 출력

Code

import sys
input = sys.stdin.readline
    
# 입력
N = int(input())
I = []
for _ in range(N):
    I.append(tuple(map(int, input().split())))
    
# 시작 시간, 회의 시간 순서대로 기준을 잡아 정렬
I.sort(key = lambda x: (x[1], x[0]))

# 회의 시작 시간이 이전 회의 끝나는 시간보다 크거나 같으면 추가
stack = [I[0]]
for index in range(1, N):
    if I[index][0] >= stack[-1][1]:
        stack.append(I[index])
print(len(stack))

메모리: 51636 KB
시간: 4420 ms