[백준] 2609, 2693, 1978, 1292, 2581번 파이썬 풀이

 

2609번: 최대공약수와 최소공배수

 

문제 설명

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

2609번: 최대공약수와 최소공배수

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

 

정답 코드

def LCM(a, b):
    for i in range(min(a,b), 0, -1):
        if (a%i == 0 and b%i == 0):
            return i

def GCD(a, b, lcm):
    return int(a * b / lcm)
    
def solution(a, b):
    lcm = LCM(a, b)
    print(lcm)
    print(GCD(a, b, lcm))
    
a, b = map(int, input().split())
solution(a, b)

 

 

 

2693번: N번 째 큰 수

 

문제 설명

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

2693번: N번째 큰 수

배열 A가 주어졌을 때, N번째 큰 값을 출력하는 프로그램을 작성하시오.

배열 A의 크기는 항상 10이고, 자연수만 가지고 있다. N은 항상 3이다.

 

정답 코드

for _ in range(int(input())):
    numbers = list(map(int, input().split()))
    print(sorted(numbers)[-3])

 

 

 

1978번: 소수 찾기

 

문제 설명

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

1978번: 소수 찾기

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

 

정답 코드

answer = int(input())
numbers = list(map(int, input().split()))

for n in numbers:
    if (n == 1):
        answer = answer - 1
        continue
    for i in range(2, n):
        if (n%i == 0):
            answer = answer - 1
            break
print(answer)

 

 

 

1292번: 쉽게 푸는 문제

 

문제 설명

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

1292번: 쉽게 푸는 문제

 

동호는 내년에 초등학교를 입학한다. 그래서 동호 어머니는 수학 선행 학습을 위해 쉽게 푸는 문제를 동호에게 주었다.

이 문제는 다음과 같다. 1을 한 번, 2를 두 번, 3을 세 번, 이런 식으로 1 2 2 3 3 3 4 4 4 4 5 .. 이러한 수열을 만들고 어느 일정한 구간을 주면 그 구간의 합을 구하는 것이다.

하지만 동호는 현재 더 어려운 문제를 푸느라 바쁘기에 우리가 동호를 도와주자.

 

문제 풀이

제법 어렵다

이 문제를 푸는데에 사용한 아이디어는 다음과 같이 두 가지이다.

1. (구현의 편리성을 위해) n까지의 합을 저장한 배열을 만든다. -> [0, 1, 3, 6, 10, 15, 21, ... ]
2. 문제의 배열을 삼각형 모양으로 생각한다.
[1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, ... , 45, 45]
->
[1,
 2, 2,
 3, 3, 3,
 4, 4, 4, 4,
 ...]
이렇게 생각하면 각 행의 원소들의 합은 행 넘버의 제곱이다.

실제로 구현할 것은 크게 두 가지 이다.
1. 1차원 배열의 인덱스가 주어졌을 때 삼각형 2차원 배열의 행과 열 넘버를 알아내는 것
2. 알아낸 행과 열 넘버로 해당 인덱스까지의 합을 구하는 것
위 두 가지를 구현하면 문제에서 요구하는 범위의 배열 합은 뒤에 것 까지의 합과 앞에 것 까지의 합을 빼면 구할 수 있다.

물론 그냥 쭉 돌면서 더해버릴 수도 있겠지만 위 방법이 조금이라도 연산 시간을 줄여줄 수 있을 것이다.

 

정답 코드

# 인덱스까지 더한 값을 배열에 저장
sums = [0]
for i in range(1, 46):
    sums.append(sums[-1] + i)

# 문제에서 제시하는 배열을 삼각형 형태의 이차원 배열로 재배치했다고 가정할 때 일차원 인덱스를 이차원의 행과 열로 변환
def findPositionInTriangle(index):
    for n in range(index, 0, -1):
        try:
            i = sums.index(n) + 1
        except ValueError:
            continue
        return (i, index - n)

def getTotalByIndex(index):
    if (index == 0):
        return 0
    i, j = findPositionInTriangle(index)
    answer = 0
    for n in range(1, i):
        answer = answer + n * n
    return answer + i * j
    
def solution(a, b):
    print(getTotalByIndex(b)-getTotalByIndex(a-1))
    
a, b = map(int, input().split())
solution(a, b)

 

 

 

2581번: 소수

 

문제 설명

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

2581번: 소수

자연수 M과 N이 주어질 때 M이상 N이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100인 경우 60이상 100이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8개가 있으므로, 이들 소수의 합은 620이고, 최솟값은 61이 된다.

 

정답 코드

primes = []

def isPrime(n):
    if n == 1:
        return False
    for i in range(2, n):
        if (n%i == 0):
            return False
    return True

def solution(a, b):
    for n in range(a, b+1):
        if (isPrime(n)):
            primes.append(n)
    if not primes:
        print(-1)
    else:
        print(sum(primes))
        print(primes[0])
    
solution(int(input()), int(input()))