AndroidTeacher

https://www.acmicpc.net/problem/9020

문제 설명

1보다 큰 자연수 중에서  1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다.

골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다.

2보다 큰 짝수 n이 주어졌을 때, n의 골드바흐 파티션을 출력하는 프로그램을 작성하시오. 만약 가능한 n의 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력한다.

풀이 과정

문제의 소수 판별 부분만 잘 구현한다면 큰 어려움 없이 풀 수 있는 문제이다.

X라는 값의 골드파티션은 a+b의 형식으로 나타나는데,

a는 2부터 X/2까지의 수 중 소수인 수이며 b는 X - a이며 소수인 수 이다.

문제에서, 골드바흐 파티션이 여러 가지인 경우에는 두 소수의 차이가 가장 작은 것을 출력하라고 했으므로

대소관계 구별을 해서 값을 갱신시켜주면 된다.

import math


def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

def goldPartition(x):
    result = []
    for i in range(2, x//2+1):
        if isPrime(i) and isPrime(x-i):
            if not result:
                result.append(i)
                result.append(x-i)
            else:
                if result[1]-result[0] > x - 2*i:
                    result[0] = i
                    result[1] = x-i

    return result


t = int(input())

for i in range(t):
    n = int(input())
    ans = goldPartition(n)

    print(*ans)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/4948

문제 설명

베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다.

이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다.

예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23)

자연수 n이 주어졌을 때, n보다 크고, 2n보다 작거나 같은 소수의 개수를 구하는 프로그램을 작성하시오. 

풀이 과정

이 문제를 풀기 위해서는 소수를 판별하는 법을 알고 있어야 한다.

소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다.

그래서 소수를 판별하는 가장 간단한 방법은

2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다.

하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다.

그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데

예를 들어, 16이라는 수가 있을 때

16의 약수는 1, 2, 4, 8, 16이며

약수들의 곱으로 나타내면 (1, 16) (2, 8) (4, 4) (8, 2) (16, 1) 다섯쌍의 곱으로 나타낼 수 있다.

이렇게 제곱근 4x4를 기준으로 양 옆으로 대칭을 이루기 때문에 제곱근 까지만 검사를 하면 된다.

이를 이용해 n+1 ~ 2n 중 소수를 판별하여 출력하면 된다.

import math

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

while True:
    n = int(input())
    if n == 0:
        break
    cnt = 0
    for i in range(n+1, 2*n+1):
        if isPrime(i):
            cnt += 1
    print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/1929

문제 설명

M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오.

풀이 과정

소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다.

그래서 소수를 판별하는 가장 간단한 방법은

2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다.

하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다.

그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데

예를 들어, 16이라는 수가 있을 때

16의 약수는 1, 2, 4, 8, 16이며

약수들의 곱으로 나타내면 (1, 16) (2, 8) (4, 4) (8, 2) (16, 1) 다섯쌍의 곱으로 나타낼 수 있다.

이렇게 제곱근 4x4를 기준으로 양 옆으로 대칭을 이루기 때문에 제곱근 까지만 검사를 하면 된다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

import math

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

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

for i in range(m, n+1):
    if isPrime(i):
        print(i)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

https://www.acmicpc.net/problem/1978

문제 설명

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

풀이 과정

소수란, 1과 자기자신을 제외한 나머지 수로 나누어 떨어지지 않는 수이다.

그래서 소수를 판별하는 가장 간단한 방법은

2부터 자기자신 - 1 까지 for문을 돌면서 나누어 떨어지는지 확인하는 것이다.

하지만, 모두 확인할 필요 없이 제곱근까지만 확인을 하면 된다.

그 이유는 약수들의 곱이 서로 대칭을 이루기 때문인데

예를 들어, 16이라는 수가 있을 때

16의 약수는 1, 2, 4, 8, 16이며

약수들의 곱으로 나타내면 (1, 16) (2, 8) (4, 4) (8, 2) (16, 1) 다섯쌍의 곱으로 나타낼 수 있다.

이렇게 제곱근 4x4를 기준으로 양 옆으로 대칭을 이루기 때문에 제곱근 까지만 검사를 하면 된다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

import math

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

def isPrime(x):
    if x == 1:
        return False
    for i in range(2, int(math.sqrt(x)) + 1):
        if x % i == 0:
            return False
    return True

cnt = 0
for num in numList:
    if isPrime(num):
        cnt += 1

print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/1011

위 링크에서 주어진 설명처럼,

시작점과 끝점이 주어질 때 공간이동 장치의 작동횟수를 구하는 문제이다.

풀이 과정

먼저, 이 문제는 규칙을 찾아 해결하는 문제이다.

규칙을 찾는 과정이 굉장히 까다로웠는데, 규칙을 찾기 위해 직접 거리 1부터 직접 테이블을 작성해보았다.

먼저 거리가 제곱수일 때를 보면 (노란 배경색), 이동 단계에 새로운 숫자가 등장한다.

그 새로운 숫자는 제곱수의 제곱근이다.

그리고 그 수를 마지노선으로 다음 거리부터 작동 횟수가 +1 늘어난다.

하지만, 이 때만 작동횟수가 늘어나는 것은 아님을 알 수 있다.

그래서 다른 규칙을 찾기 위해 다음과 같은 방법을 이용해보았다.

표의 작동횟수 부분을 보면 작동횟수가 늘어나는데에는 다음과 같은 규칙이 있다.

위에서부터 작동횟수가 나타나는 규칙을 살펴보면

횟수1은 1번나타나고, 2도 1번 나타나지만 3은 2번, 4도 2번 나타난다.

[1-> 1번] [2-> 1번] [3-> 2번] [4-> 2번] [5-> 3번] [6-> 3번] [7-> 4번] [8-> 4번]...

이런 형식으로 나타남을 알 수 있는데,

[N-> M번] 에서 M번이 모두 2번씩 나타남을 알 수 있다.

이 규칙을 이용하면 거리에 따른 작동횟수를 구할 수 있다.

초기 이동거리는 0인 상태이며 작동 횟수도 0회이고 이동할 거리는 1로 고정이다.

그리고 위에서 설명한 것 처럼 작동횟수가 1, 2, 3, 3, 4, 4, 5, 5, 5, 6 ,6 ,6 ,7 ,7, 7, 7, 8, 8, 8, 8 ... 처럼

각 횟수가 나타나는 횟수가 2번이기 때문에

홀 수가 될 때 마다 각 작동횟수가 나타나는 횟수가 1씩 증가하므로

홀수일 때 마다 step(이동할 거리)를 1씩 높여준다.

(3번 나타나는 경우는 표의 행을 3칸 건너뛰고

2번 나타나는 경우는 표의 행을 2칸 건너뛰기 때문에)

설명이 조금 어려울 수 있는데, 이해가 잘 안된다면 위의 표처럼 직접 그려서 확인해보는 것을 추천한다.

t = int(input())

for i in range(t):
    x, y = map(int, input().split())
    dist = y - x
    step = 1        # 이동할 거리(초기는 1)
    cnt = 0         # 작동 횟수
    mydist = 0      # 초기 이동거리는 0

    while mydist < dist:
        cnt += 1
        mydist += step

        if cnt % 2 == 0:
            step += 1

    print(cnt)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/2775

평소 반상회에 참석하는 것을 좋아하는 주희는 이번 기회에 부녀회장이 되고 싶어 각 층의 사람들을 불러 모아 반상회를 주최하려고 한다.

이 아파트에 거주를 하려면 조건이 있는데, “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다” 는 계약 조항을 꼭 지키고 들어와야 한다.

아파트에 비어있는 집은 없고 모든 거주민들이 이 계약 조건을 지키고 왔다고 가정했을 때, 주어지는 양의 정수 k와 n에 대해 k층에 n호에는 몇 명이 살고 있는지 출력하라. 단, 아파트에는 0층부터 있고 각층에는 1호부터 있으며, 0층의 i호에는 i명이 산다.

풀이 과정

먼저 0층 n호에는 n명이 살고 있으므로 0층은 [ 1, 2, 3, 4, 5... ]으로 설정을 해준다.

1층의 n호에는 0층 1호 ~ n호까지의 사람수만큼 살고 있으므로 sum(0층의 1호~n호)가 되며

2층의 n호에는 1층 1호 ~ n호까지의 사람수만큼 살고 있으므로 sum(1층의 1호~n호)가 된다.

이렇게 1층부터는 이전층의 사람수들을 누적으로 합해감을 알 수 있다.

이를 파이썬으로 나타낸 코드는 다음과 같다.

t = int(input())

for _ in range(t):
    k = int(input())
    n = int(input())
    graph = [[0]*n for _ in range(k+1)]

    graph[0] = [i+1 for i in range(n)]

    for i in range(1, k+1):
        for j in range(n):
            graph[i][j] = sum(graph[i-1][:j+1])

    print(graph[k][n-1])

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/10250

문제의 설명이 그림과 함께 길게 제공되므로 위 링크를 참조바랍니다.

풀이 과정

1203 이라는 호수가 있을 때

앞의 두자리 12를 층수, 뒤의 두자리 03을 호수라고 하자.

핵심적인 부분은 손님들을 먼저 층수를 우선순위로 채우고,

그 다음 호수를 채워나간다. 

즉 하나의 열에 대해 모든 행을 채운 후에, 그 다음 열로 이동하여 모든 행을 채우는 형식이다.

그래서, n % h를 통해 몇 번째 행에 들어갈지를 결정하면 되고

(n - 1 ) // h + 1을 통해 몇 번째 열에 들어갈지를 결정하면 된다.

이 때, 뒤의 호수는 3처럼 한 자리더라도, 두 자리를 유지해야 하므로

10보다 작을 경우 앞에 0을 붙여준다.

t = int(input())

for i in range(t):
    h, w, n = map(int, input().split())

    floor = n % h
    if floor == 0:
        floor = h
    hosu = (n - 1) // h + 1
    if hosu < 10:
        hosu = "0" + str(hosu)

    answer = str(floor) + str(hosu)
    print(answer)

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !

문제 설명

https://www.acmicpc.net/problem/1110

0보다 크거나 같고, 99보다 작거나 같은 정수가 주어질 때 다음과 같은 연산을 할 수 있다. 먼저 주어진 수가 10보다 작다면 앞에 0을 붙여 두 자리 수로 만들고, 각 자리의 숫자를 더한다. 그 다음, 주어진 수의 가장 오른쪽 자리 수와 앞에서 구한 합의 가장 오른쪽 자리 수를 이어 붙이면 새로운 수를 만들 수 있다. 다음 예를 보자.

26부터 시작한다. 2+6 = 8이다. 새로운 수는 68이다. 6+8 = 14이다. 새로운 수는 84이다. 8+4 = 12이다. 새로운 수는 42이다. 4+2 = 6이다. 새로운 수는 26이다.

위의 예는 4번만에 원래 수로 돌아올 수 있다. 따라서 26의 사이클의 길이는 4이다.

N이 주어졌을 때, N의 사이클의 길이를 구하는 프로그램을 작성하시오.

풀이 과정

문제에서 주어진 조건을 그대로 코드로 옮겨 구현하면 되는 문제이다.

10보다 작은 경우는 앞에 0을 붙여 두자리 수로 만들어야 한다고 했으므로

입력은 int형이 아닌 string형으로 받아 0을 붙이기 쉽도록 하자.

그 후에는, 문제에서 주어진 조건대로 수를 바꿔주면 된다.

바꾸기전의 마지막 자리수와 바꾸기 전의 첫번째 자리 + 두번째 자리를 더한 수의 마지막 자리를 더한 수가

다음 숫자가 되는 규칙이다.

핵심은 while문 혹은 재귀함수를 통해 수를 규칙대로 바꿔주는 것이다.

n = input()
tmp = n

if int(n) < 10:
    tmp = "0" + n

cnt = 0
while True:
    cnt += 1

    second = str(int(tmp[0]) + int(tmp[-1]))[-1]
    first = tmp[-1]

    ans = first + second

    if int(ans) == int(n):
        print(cnt)
        break
    else:
        tmp = ans