지능형 기차 (2455)

문제

최근에 개발된 지능형 기차가 1번역(출발역)부터 4번역(종착역)까지 4개의 정차역이 있는 노선에서 운행되고 있다. 이 기차에는 타거나 내리는 사람 수를 자동으로 인식할 수 있는 장치가 있다. 이 장치를 이용하여 출발역에서 종착역까지 가는 도중 기차 안에 사람이 가장 많을 때의 사람 수를 계산하려고 한다. 단, 이 기차를 이용하는 사람들은 질서 의식이 투철하여, 역에서 기차에 탈 때, 내릴 사람이 모두 내린 후에 기차에 탄다고 가정한다.

내린 사람 수탄 사람 수
1번역(출발역)032
2번역313
3번역2825
4번역(종착역)390

예를 들어, 위와 같은 경우를 살펴보자. 이 경우, 기차 안에 사람이 가장 많은 때는 2번역에서 3명의 사람이 기차에서 내리고, 13명의 사람이 기차에 탔을 때로, 총 42명의 사람이 기차 안에 있다.

이 기차는 다음 조건을 만족하면서 운행된다고 가정한다.

  1. 기차는 역 번호 순서대로 운행한다.
  2. 출발역에서 내린 사람 수와 종착역에서 탄 사람 수는 0이다.
  3. 각 역에서 현재 기차에 있는 사람보다 더 많은 사람이 내리는 경우는 없다.
  4. 기차의 정원은 최대 10,000명이고, 정원을 초과하여 타는 경우는 없다.

4개의 역에 대해 기차에서 내린 사람 수와 탄 사람 수가 주어졌을 때, 기차에 사람이 가장 많을 때의 사람 수를 계산하는 프로그램을 작성하시오.

입력

각 역에서 내린 사람 수와 탄 사람 수가 빈칸을 사이에 두고 첫째 줄부터 넷째 줄까지 역 순서대로 한 줄에 하나씩 주어진다.

출력

첫째 줄에 최대 사람 수를 출력한다.

예제 입력

0 32
3 13
28 25
39 0

예제 출력

42

풀이

passengers = 0 # 현재 기차에 탄 승객
peak = [] # 각 정차 역 마다 내리고 탑승한 이후의 값 저장

for _ in range(4):
    leave, enter = map(int, input().split())
    passengers -= leave
    passengers += enter
    peak.append(passengers) # 리스트에 현재 기차 내 승객을 추가

print(max(peak)) # 열차에 사람이 가장 많았을 때의 승객 수를 출력

소수 찾기 (1978)

문제

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

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

출력

주어진 수들 중 소수의 개수를 출력한다.

예제 입력

4
1 3 5 7

예제 출력

3

풀이

import math # 내장 라이브러리 포함

n = int(input()) # 변수 n 입력

x = list(map(int, input().split())) # 입력받은 n개의 수를 리스트에 입력

count = 0 # 주어진 수들 중 소수의 개수

for i in x:
    if i <= 1: # 1은 소수가 아니므로 i가 1일 때 continue
        continue
    prime = True # i를 소수로 가정
    # 정수 i의 제곱근 이하의 값까지만 검사하면 나머지는 검사할 필요가 없다.
    # 예를 들어 i가 24라면 i의 제곱근은 약 4.898이다.
    # 이때, i의 제곱근과 곱해서 i가 되는 약수들을 나열해보면 다음과 같다.
	# 1 * 24
	# 2 * 12
	# 3 * 8
	# 4 * 6
	# 4.898 * 4.898
	# 6 * 4
	# 8 * 3
	# 12 * 2
	# 24 * 1
	# 여기서 i의 제곱근인 약 4.898을 기준으로 약수들의 곱이 대칭이 되는 것을 확인할 수 있다.
	# 이러한 원리를 이용하면 i까지 반복할 필요 없이 좀 더 빠르게 소수를 구하는 것이 가능하다.
    for j in range(2, int(math.sqrt(i)) + 1): # 2 ~ i의 제곱근까지 반복하기
        if i % j == 0: # 만약 i가 j로 나누어 떨어질 때 i가 소수라는 가정은 거짓이 됨
            prime = False
            break # 소수가 아님을 판별했으므로 반복문 종료
    if prime: count += 1 # 만약 i가 소수면 1을 더한다.

print(count) # 최종적으로 소수의 개수 출력