컴공0개언어

문제 링크 : www.acmicpc.net/problem/1003

key로 숫자, value로 (0이 출력되는 횟수, 1이 출력되는 횟수)를 저장하는 counts 딕셔너리를 이용하였다.

fibonacci(0)이 호출되었을 때는 0이 출력되는 횟수가 1, 1이 출력되는 횟수가 0이므로 counts[0]은 (1, 0)으로 초기화하고, 같은 방법으로 counts[1]은 (0, 1)로 초기화 하였다.

따라서 counts[i]는 (counts[i-1][0] + counts[i-2][0], counts[i-1][1] + counts[i-2][1])가 된다.

import sys

counts = {0: (1, 0), 1: (0, 1)} # key: num, value: (0이 출력되는 횟수, 1이 출력되는 횟수)

def fibonacci(n):
    if n == 0: return 0
    if n == 1: return 1

    for i in range(2, n+1):
        counts[i] = (counts[i-1][0] + counts[i-2][0], counts[i-1][1] + counts[i-2][1])


N = int(sys.stdin.readline())

for _ in range(N):
    n = int(sys.stdin.readline())

    if n in counts:
        print(counts[n][0], end=' ')
        print(counts[n][1])
    else:
        fibonacci(n)

        print(counts[n][0], end=' ')
        print(counts[n][1])

문제 링크 : www.acmicpc.net/problem/14888

입력받은 연산자들에 대해서 itertools에 있는 permutation에 대해서 가능한 모든 경우에 대해서 계산을 진행하여 최대/최소값을 구하였다.

import sys
from itertools import permutations

#  1-2÷3+4+5×6 ==> 54
def get_result(nums, ops):
    N = len(nums)
    result = 0

    if ops[0] == '+':
        result = nums[0] + nums[1]
    elif ops[0] == '-':
        result = nums[0] - nums[1]
    elif ops[0] == 'x':
        result = nums[0] * nums[1]
    elif ops[0] == '/':
        if nums[0] < 0 or nums[1] < 0:
            result = -(abs(nums[0]) // abs(nums[1]))
        else:
            result = nums[0] // nums[1]

    for i in range(1, N-1):
        if ops[i] == '+':
            result = result + nums[i+1]
        elif ops[i] == '-':
            result = result - nums[i+1]
        elif ops[i] == 'x':
            result = result * nums[i+1]
        elif ops[i] == '/':
            if result < 0 or nums[i+1] < 0:
                result = -(abs(result) // abs(nums[i+1]))
            else:
                result = result // nums[i+1]

    return result

N = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
op_count = list(map(int, sys.stdin.readline().split())) # + - x %
ops = ['+'] * op_count[0] + ['-'] * op_count[1] + ['x'] * op_count[2] + ['/'] * op_count[3]

min_result = sys.maxsize
max_result = -sys.maxsize
for permutation in permutations(ops, N-1):
    temp_result = get_result(nums, permutation)

    if min_result > temp_result:
        min_result = temp_result

    if max_result < temp_result:
        max_result = temp_result

print(max_result)
print(min_result)

문제 링크 : www.acmicpc.net/problem/15650

조합의 경우들을 출력하는 것으로, itertools에 있는 combinations를 사용하면 간단하게 해결할 수 있다.

import sys
from itertools import combinations

N, M = map(int, sys.stdin.readline().split())
nums = list(range(1, N+1))

for combination in combinations(nums, M):
    print(*combination)

문제 링크 : www.acmicpc.net/problem/15649

순열 경우의 수들을 출력하는 것으로, itertools에 있는 permutations()을 이용하면 간단하게 해결할 수 있다.

import sys
from itertools import permutations

N, M = map(int, sys.stdin.readline().split())
nums = list(range(1, N+1))

for permutation in permutations(nums, M):
    print(*permutation)

문제 링크 : www.acmicpc.net/problem/14891

deque를 이용하여 문제를 해결하였다. 먼저 톱니바퀴 위치에 따른 index는 다음과 같다.

따라서 왼쪽 톱니바퀴의 회전 여부를 판단할 때는 현재 톱니바퀴에서 index가 6인 원소의 값과 왼쪽 톱니바퀴에서 index가 2인 원소의 값을 비교하고, 오른쪽 톱니바퀴의 회전 여부를 판단할 때는 현재 톱니바퀴에서 index가 2인 원소의 값과 오른쪽 톱니바퀴에서 index가 6인 원소의 값을 비교한다.

그리고 N극은 0, S극은 1이므로 위의 톱니바퀴를 deque로 나타내면 "01011111"이고, 시계방향과 반시계 방향으로 회전했을 때의 값은 다음과 같다.

 따라서 시계 방향으로 회전시킬 경우 deque.appendleft(deque.pop()), 반시계 방향으로 회전시킬 경우 deque.append(deque.popleft())를 사용한다.

import sys
from collections import deque

# N극 : 0, S극 : 1
# 초록색 판단 부분 index : 2, 6
wheels = [deque(list(sys.stdin.readline().rstrip())) for _ in range(4)]

def init_rotate(wheel_num, direction):
    if 1 <= wheel_num <= 3:
        # 오른쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][2] != wheels[wheel_num][6]:
            rotate(wheel_num+1, -1*direction, True)

    if 2 <= wheel_num <= 4:
        # 왼쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][6] != wheels[wheel_num-2][2]:
            rotate(wheel_num-1, -1*direction, False)

    if direction == 1:  # 시계
        wheels[wheel_num - 1].appendleft(wheels[wheel_num - 1].pop())
    elif direction == -1:  # 반시계
        wheels[wheel_num - 1].append(wheels[wheel_num - 1].popleft())


def rotate(wheel_num, direction, next_right=True):
    if next_right and 1 <= wheel_num <= 3:
        # 오른쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][2] != wheels[wheel_num][6]:
            rotate(wheel_num+1, -1*direction, True)

    if not next_right and 2 <= wheel_num <= 4:
        # 왼쪽 톱니바퀴 회전 판단
        if wheels[wheel_num-1][6] != wheels[wheel_num-2][2]:
            rotate(wheel_num-1, -1*direction, False)

    if direction == 1:  # 시계
        wheels[wheel_num - 1].appendleft(wheels[wheel_num - 1].pop())
    elif direction == -1:  # 반시계
        wheels[wheel_num - 1].append(wheels[wheel_num - 1].popleft())

def calc_score():
    score = 0

    for i, wheel in enumerate(wheels):
        if wheel[0] == '1':
            score += 2 ** i

    return score


K = int(sys.stdin.readline())

for _ in range(K):
    # wheel_num : 회전시키는 톱니바퀴 번호, direction: 1이면 시계방향, -1이면 반시계방향
    wheel_num, direction = map(int, sys.stdin.readline().rstrip().split())

    init_rotate(wheel_num, direction)

print(calc_score())

init_rotate()와 rotate()를 합치고 싶었는데 생각보다 쉽지 않아서 하지 못한 점이 아쉽다.

문제 링크 : www.acmicpc.net/problem/1449

① 처음 테이프 시작 지점(start)을 (처음 물이 새는 위치 - 0.5), 마지막 지점(end)을 (처음 물이 새는 위치 + 0.5)로 설정 

② 물이 새는 위치를 하나씩 가져오면서 마지막 지점을 (현재 물이 새는 위치 + 0.5)로 갱신하고, (end-start)값이 테이프의 길이보다 큰지 확인

③ 크면 이전 물이 새는 위치까지 막을 수 있다는 것이므로, 테이프 개수를 1 증가하고 테이프 시작 지점을 (현재 물이 새는 위치 - 0.5)로 갱신하고 동일한 과정을 반복

④ 마지막 (start-end)값이 테이프 길이와 같거나, 마지막 물이 새는 위치가 하나 남았을 때에도 막아야하므로 (end-start)이 1이상이면 테이프 개수 1 증가

처음 소스코드를 제출했을 때 맞게 작성한 것 같았는데 틀려서 살펴보니 정렬을 하지 않은 상태에서 진행했었다. 예제에서는 물이 새는 위치가 오름차순으로 입력되어 있어서 정렬을 안해도 될 것 같지만 문제를 살펴보면 내림차순 or 오름차순으로 입력한다는 부분이 없으므로 물이 새는 위치를 오름차순으로 정렬한 후 진행해야한다. 

import sys

N, L = map(int, sys.stdin.readline().split())

locations = list(map(int, sys.stdin.readline().split()))
locations.sort() # 위치가 오름차순 or 내림차순으로 입력된다는 조건이 없으므로

tape_count = 0
start = locations[0] - 0.5
end = locations[0] + 0.5
for loc in locations:
    end = loc + 0.5

    if (end - start) > L:
        tape_count += 1
        start = loc - 0.5

if (end - start) >= 1:
    tape_count += 1

print(tape_count)

문제링크 : www.acmicpc.net/problem/4796

그렇게 어려운 문제는 아니었다. 첫 날부터 캠핑장을 사용한다고 하면 최대 캠핑장 사용 일수를 구할 수 있다.

구체적으로는 V일 중 P일의 사이클이 V//P번 완전하게 반복하므로 L*(V//P)일동안 캠핑장을 사용하고, 마지막 부분은 V%P와 L중 작은 값 만큼 캠핑장을 사용한다. 따라서 캠핑장 최대 사용일은 L*(V//P) + min(V%P, L)이다. 

예제로 주어진 L=5, P=8, V=20일 경우를 살펴보면

V//P = 2이므로 P일의 사이클이 2번 반복되므로 16일까지 10번 캠핑장을 이용하고, V%P = 4, L=5이므로 마지막 4일동안 모두 캠핑장을 사용하므로 총 14일동안 캠핑장을 이용한다. 소스코드는 다음과 같다.

import sys

i = 0
while True:
    L, P, V = map(int, sys.stdin.readline().rstrip().split())

    if L == 0 and P == 0 and V == 0:
        break

    print('Case %d: %d' % (i+1, L*(V//P) + min(V%P, L)))

    i += 1

문제 링크 : www.acmicpc.net/problem/2217

처음에 나타난 최대 중량을 구하는 방법을 찾는데 시간이 조금 걸렸다. 로프가 버틸 수 있는 최대 중량은 (선택한 로프들의 버틸 수 있는 중량 중 최솟값) x (선택한 로프의 개수)이다. 따라서 예제를 살펴보면 로프가 2개가 있고, 버틸 수 있는 중량이 10, 15이다. 여기서 로프를 모두 사용할 필요는 없으므로 가능한 경우의 수는 2가지이다.

① 버틸 수 있는 중량이 15인 로프만 사용 ==>  버틸 수 있는 중량 = 15 x 1 = 15

② 버틸 수 있는 중량이 10인 로프만 사용 ==> 버틸 수 있는 중량 = 10 x 1 = 10

③ 두 개의 로프를 모두 사용 ==> 버틸 수 있는 중량 = 10 x 2 = 20

따라서 버틸 수 있는 최대 중량은 20이다.

이를 통해 생각한 문제풀이 방법은 다음과 같다.

① 중량들을 내림차순으로 정렬하고, 최대 중량을 첫 번째 원소의 값으로 초기화

② 다음 로프가 추가되었을 때의 중량이 최대 중량보다 크면 최대 중량을 갱신

import sys

N = int(sys.stdin.readline())
ropes = []
for _ in range(N):
    rope = int(sys.stdin.readline())
    ropes.append(rope)

ropes.sort(reverse=True)

weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
    weight = rope * (i+1)

    if weight > max_weight:
        max_weight = weight

print(max_weight)

제출 후 다른 분들의 코드를 살펴보았는데 리스트 표현식, max()함수 등을 이용하여 소스코드를 간결하게 작성이 가능했다. 따라서 간결한 버전의 소스코드는 다음과 같다.

import sys

N = int(sys.stdin.readline())
ropes = [int(sys.stdin.readline()) for _ in range(N)]

ropes.sort(reverse=True)

weight = 0
max_weight = ropes[0]
for i, rope in enumerate(ropes):
    max_weight = max(max_weight, rope*(i+1))
    
print(max_weight)