효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

코드

import sys
input=sys.stdin.readline

n=int(input())
wine=[]
for _ in range(n):
    wine.append(int(input()))

dp=[0]*n
dp[0]=wine[0]
if n>=2:
    dp[1]=wine[0]+wine[1]
if n>=3:
    dp[2]=max(wine[0]+wine[1], wine[1]+wine[2], wine[0]+wine[2])

for i in range(3,n):
    dp[i]=max(dp[i-1], wine[i]+wine[i-1]+dp[i-3], wine[i]+dp[i-2])

print(dp[n-1])

문제 해결

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

코드

import sys
input=sys.stdin.readline

n=int(input())
dp=[0 for _ in range(31)]
dp[2]=3
for i in range(4,n+1,2):
    dp[i]=3*dp[i-2]+(sum(dp[:i-2])+1)*2

print(dp[n])

문제 해결

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

코드

import sys
input=sys.stdin.readline

data=[]
n, c =map(int, input().split())
for i in range(n):
    data.append(int(input()))

data.sort()
start, end=1, data[-1]-data[0]
answer=0

while start<=end:
    mid=(start+end)//2
    router=data[0]
    count=1

    for i in range(1, len(data)):
        if data[i]>= router+mid:
            count+=1
            router=data[i]
    if count >=c:
        start = mid +1
        answer = mid
    else:
        end=mid-1

print(answer)

문제 해결

이분 탐색을 활용한 코드이고 생각보다 코드를 작성하기 어려웠다

문제의 접근 순서는 다음과 같다.

1. 주어진 집들의 좌표를 오름차순으로 정렬한다 (이분 탐색의 기본 조건).
2. 집들 사이의 거리를 초기화한다. 최솟값은 1이며, 최댓값은 끝집과 첫집 사이의 거리이다.
3. 집들 사이의 거리를 기준으로 이분 탐색을 진행한다. 주어진 간격 (mid)으로 공유기를 설치했을 때, 주어진 조건을 충족하는지 확인한다.
4. 3번을 만족하는 거리들 중 최댓값을 출력한다.

수를 처리하는 것은 통계학에서 상당히 중요한 일이다. 통계학에서 N개의 수를 대표하는 기본 통계값에는 다음과 같은 것들이 있다. 단, N은 홀수라고 가정하자.

1. 산술평균 : N개의 수들의 합을 N으로 나눈 값
2. 중앙값 : N개의 수들을 증가하는 순서로 나열했을 경우 그 중앙에 위치하는 값
3. 최빈값 : N개의 수들 중 가장 많이 나타나는 값
4. 범위 : N개의 수들 중 최댓값과 최솟값의 차이

N개의 수가 주어졌을 때, 네 가지 기본 통계값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 단, N은 홀수이다. 그 다음 N개의 줄에는 정수들이 주어진다. 입력되는 정수의 절댓값은 4,000을 넘지 않는다.

출력

첫째 줄에는 산술평균을 출력한다. 소수점 이하 첫째 자리에서 반올림한 값을 출력한다.

둘째 줄에는 중앙값을 출력한다.

셋째 줄에는 최빈값을 출력한다. 여러 개 있을 때에는 최빈값 중 두 번째로 작은 값을 출력한다.

넷째 줄에는 범위를 출력한다.

코드

import sys
n=int(sys.stdin.readline())
a=[]
total=0
for i in range(n):
  a.append(int(sys.stdin.readline()))
  total+=a[i]

print(round(total/n))
a.sort(reverse=True)
print(a[n//2])

dict={}
for i in range(n):
  if a[i] in dict:
    dict[a[i]]+=1
  else:
    dict[a[i]]=1

sorted_dict = sorted(dict.items(), key = lambda item: item[1], reverse = True)
maxcnt=1
b=[]
for i in sorted_dict:
  if i[1]>=maxcnt:
    b.append(i[0])
    maxcnt=i[1]
  else:
    break
    
if len(b)==1 :
  print(b[0])
else:
  b.sort(reverse=True)
  print(b[-2])

print(-a[n-1]+a[0])

문제 해결

-2진법은 부호 없는 2진수로 표현이 된다. 2진법에서는 20, 21, 22, 23이 표현 되지만 -2진법에서는 (-2)0 = 1, (-2)1 = -2, (-2)2 = 4, (-2)3 = -8을 표현한다. 10진수로 1부터 표현하자면 1, 110, 111, 100, 101, 11010, 11011, 11000, 11001 등이다.

10진법의 수를 입력 받아서 -2진수를 출력하는 프로그램을 작성하시오.

첫 줄에 10진법으로 표현된 수 N이 주어진다.

출력

-2진법 수를 출력한다.

제한

• -2,000,000,000 ≤ N ≤ 2,000,000,000