190129 백준 알고리즘 문제풀기*

|

[2775] 부녀회장이 될테야

문제

  • case 수, 층 수, 호 수가 차례대로 입력 됨
  • 0층은 호수대로 1명, 2명, 3명, … 이 살고, 1층부터는 자신의 호수에 해당하는 밑에 층 사람들의 누적 합 만큼 산다.
    • 예를 들어, 1층 3호는 0층의 1호, 2호, 3호 인원들의 합인 1 + 2 + 3 = 6명이 산다.

정답

for _ in range(int(input())):
    k = int(input())
    n = int(input())
    room = [[0 for x in range(n)] for y in range(k+1)]
    for j in range(n):
        room[0][j] = j + 1
    for j in range(1, k+1):
        for i in range(n):
            s = 0
            if i==0:
                room[j][i] = 1
            else:
                for x in range(i + 1):
                    s += room[j-1][x]
                room[j][i] = s
    print(room[k][n-1])

[1475] 방 번호

문제

  • 한 숫자세트는 0~9의 숫자 하나로 이루어짐
  • 6은 뒤집어서 9로 서로 교차사용이 가능하다
  • 방 번호가 주어질 때, 최소로 필요한 숫자세트의 개수를 출력

  • 6과 9의 갯수의 합이 홀/짝일때의 별도 처리가 필요하다.

정답

a = str(input())
nums = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
for j in range(len(a)):
    nums[int(a[j])] += 1
sixes = nums[6] + nums[9]
if sixes%2==0:
    nums[6] = int(sixes/2)
else:
    nums[6] = int(sixes/2) + 1
nums[9] = 0
print(sorted(nums)[9])

[6064] 카잉달력*

문제

  • 근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. 의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. 은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.
  • 예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.
  • 네 개의 정수 M, N, x와 y가 주어질 때, 이 카잉 달력의 마지막 해라고 하면 는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

정답

def getyear(m, n, x, y):
    while x<=m*n:
        if (x-y)%n == 0:
            return x
        x += m
    return -1
for _ in range(int(input())):
    m, n, x, y = map(int, input().split())
    print(getyear(m, n, x, y))