💡 해당 글은 이코테 2021 강의 몰아보기를 보고 개인적으로 정리한 글입니다. 문제 시 삭제하겠습니다!
💡 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전히 무한히 존재한다고 가정합니다. 손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.
Q. 가장 큰 화폐 단위부터 돈을 거슬러 주는 것이 최적의 해를 보장하는 이유
A. 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로, 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문
n = 1250
count = 0
# 큰 단위의 화폐부터 차레대로 확인하기
array = [500, 100, 50, 10]
for cont in array:
count += n // coint # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
n %= coin
print(count)
N
이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단 2번째 연산은 N
이 K
로 나누어 떨어질 때만 선택할 수 있다.N
에서 1을 뺀다.N
을 K
로 나눈다.N
이 17, K
가 4라고 가정하자. 이때 1번 과정을 한 번 수행하면 N
은 16이 되고, 이후에 2번 과정을 두 번 수행하면 N
은 1이 된다. 결과적으로 이 경우 전체 과정을 실행한 횟수는 3이 된다. 이는 N
을 1로 만드는 최소 횟수이다.N
과 K
가 주어질 때 N
이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 최소 횟수를 구하라.N
(1 <= N
<= 100,000)과 K
(2 <= K
<= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어진다.25 5
N
이 1이 될 때까지 1번 또는 2번 과정을 수행해야 하는 횟수의 최솟값을 출력한다.2
💫
K
로 나눌 수 있으면K
로 나누고, 나눌 수 없으면 1을 빼는 과정을N
이 1이 될 때까지 반복
N
에 대해 최대한 많이 나누기를 수행하면 됨N
의 값을 줄일 때, 2 이상의 수로 나누는 작업이 1을 빼는 작업보다 수를 훨씬 많이 줄일 수 있음N
= 25, K
= 3일 때 다음과 같음K
가 2 이상이므로, K
로 나누는 것이 1을 빼는 것보다 항상 빠르게 N
을 줄일 수 있음N
은 항상 1에 도달하게 됨(최적의 해 성립)# N, K을 공백을 기준으로 구분하여 입력 받기
n, k = map(int, inpu().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지 빼기
target = (n // k) * k
result += (n - target)
n = target
# N이 K보다 작을 때 (더이상 나눌 수 없을 때) 반복문 탈출
if n < k:
break
# K로 나누기
result += 1
n //= k
# 마지막으로 남은 수에 더하여 1씩 빼기
result += (n - 1)
print(result)
target = (n // k) * k
코드는 n
이 k
로 나누어 떨어지지 않는다고 할 때, k
로 나누어 떨어질 수 있는 가장 가까운 수를 구하는 트릭각 자리가 숫자(0~9)로만 이루어진 문자열 S
가 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 'x' 혹은 '+' 연산자를 넣어 결과적으로 만들어질 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.
단, +보다 x를 먼저 계산하는 일반적인 방식과는 달리, 모든 연산은 왼쪽에서부터 순서대로 이루어진다고 가정한다.
예를 들어, 02984
라는 문자열로 만들 수 있는 가장 큰 수는 (((((0+2) x 9) x 8) x 4) = 576
이다. 또한 만들어질 수 있는 가장 큰 수는 항상 20억 이하의 정수가 되도록 입력이 주어진다.
입력 조건 : 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S
가 주어진다. (1 <= S
의 길이 <= 20)
02984
576
💫
0일 때만 더하고 나머지는 다 곱한다...?
0, 1일 때만 더하고 나머지는 다 곱하기
0
또는 1
인 경우, 곱하기 보다 더하기를 수행하는 것이 효율적data = input()
# 첫 번째 문자를 숫자로 변경하여 대입
result = int(data[0])
for i in range(1, len(data)):
# 두 수 중에서 하나라도 '0' 혹은 '1'인 경우, 곱하기보다는 더하기 수행
num = int(data[i])
if num <= 1 or result <= 1:
result += num
else:
result *= num
print(result)
N
명 있다. 모험가 길드에서는 N
명 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.X
인 모험가는 반드시 X
명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.N
명의 모험가에 대한 정보가 주어졌을 때, 여행을 떠날 수 있는 그룹 수의 최댓값을 구하는 프로그램을 작성하시오.N
이 5이고, 각 모험가의 공포도가 다음과 같다고 가정하자.2 3 1 2 2
N
이 주어지고(1 <= N
<= 100,000), 둘째 줄에 각 모험가의 공포도의 값을 N
이하의 자연수로 주어지며, 각 자연수는 공백으로 구분한다.5
2 3 1 2 2
2
💫 예시 답안이 (1,2,3), (2,2) 이거라서 감을 못 잡았음...ㅠㅠ (1), (2,2) 이렇게 해도 그룹 수는 같은데,,,
n = int(input())
data = list(map(int, input().split()))
data.sort()
result = 0 # 총 그룹 수
count = 0 # 현재 그룹에 포함된 모험가의 수
for i in data: # 공포도를 낮은 것부터 하나씩 확인하며
count += 1 # 현재 그룹에 해당 모험가를 포함시키기
if count >= i: # 현재 그룹에 포함된 모험가의 수가 현재의 공포도 이상이라면, 그룹 결성
result += 1 # 총 그룹의 수 증가시키기
count = 0 # 현재 그룹에 포함된 모험가의 수 초기화
print(result) # 총 그룹의 수 출력
# 동, 북, 서, 남
dx = [0, -1, 0, 1]
dy = [1, 0, -1, 0]
# 현재 위치
x, y = 2, 2
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
print(nx, ny)
여행가 A는 N
x N
크기의 정사각형 공간 위에 서 있다. 이 공간은 1 x 1 크기의 정사각형으로 나누어져 있다. 가장 왼쪽 위 좌표는 (1, 1)이며, 가장 오른쪽 아래 좌표는 (N
, N
)에 해당한다. 여행가 A는 상, 하, 좌, 우 방향으로 이동할 수 있으며, 시작 좌표는 항상 (1, 1)이다. 우리 앞에는 여행가 A가 이동할 계획이 적힌 계획서가 놓여 있다.
계획서에는 하나의 줄에 띄어쓰기를 기준으로 하여 L, R, U, D 중 하나의 문자가 반복적으로 적혀 있다.
이때 여행가 A가 N
x N
크기의 정사각형 공간을 벗어나는 움직임은 무시된다.
입력 조건 : 첫째 줄에 공간의 크기를 나타내는 N
이 주어지고(1 <= N
<= 100), 둘째 줄에 여행가 A가 이동할 계획서 내용이 주어진다.(1 <= 이동 횟수 <= 100)
5
R R R U D D
3 4
# N 입력 받기
n = int(input())
x, y = 1, 1
plans = input().split()
# L, R, U, D에 따른 이동 방향
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]
move_types = ['L', 'R', 'U', 'D']
# 이동 계획을 하나씩 확인하기
for plan in plans:
# 이동 후 좌표 구하기
for i in range(len(move_types)):
if plan == move_types[i]:
nx = x + dx[i]
ny = y + dy[i]
# 공간을 벗어나는 경우 무시
if nx < 1 or ny < 1 or nx > n or ny > n:
continue
# 이동 수행
x, y = nx, ny
print(x, y)
N
이 입력되면 00시 00분 00초부터 N
시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 1을 입력했을 때, 다음은 3이 하나라도 포함되어 있으므로 세어야 하는 시각이다.N
이 입력된다. (0 <= N
<= 23)5
N
시 59분 59초까지의 모든 시각 중에서 3이 하나라도 포함되는 모든 경우의 수를 출력한다.11475
💫
N
이 3, 13, 23인지 확인해서 60 * 60만큼 세어주고, 나머지 '시'동안 '분'에 3이 들어가는 것들 세어주고, 나머지 '초'동안 3이 들어가는 것들 세기.
# H 입력 받기
h = int(input())
count = 0
for i in range(h + 1):
for j in range(60):
for k in range(60):
# 매 시각 안에 '3'이 포함되어 있다면 카운트 증가
if '3' in str(i) + str(j) + str(k):
count += 1
print(count)
행복 왕국의 왕실 정원은 체스판과 같은 8 x 8 좌표 평면이다. 왕실 정원의 특정한 한 칸에 나이트가 서 있다. 나이트는 매우 충성스러운 신하로서 매일 무술을 연마한다.
나이트는 말을 타고 있기 때문에 이동을 할 때는 L자 형태로만 이동할 수 있으며 정원 밖으로는 나갈 수 없다.
나이트는 특정 위치에서 다음과 같은 2가지 경우로 이동할 수 있다.
이처럼 8 x 8 좌표 평면상에서 나이트의 위치가 주어졌을 때, 나이트가 이동할 수 있는 경우의 수를 출력하는 프로그램을 작성하시오. 왕실의 정원에서 행 위치를 표현할 때는 1부터 8로 표현하며, 열 위치를 표현할 때는 a부터 h로 표현한다.
입력 조건 : 첫째 줄에 8 x 8 좌표 평면상에서 현재 나이트가 위치한 곳의 좌표를 나타내는 두 문자로 구성된 문자열이 입력된다. 입력 문자는 a1처럼 열과 행으로 이루어진다.
a1
2
# 현재 나이트의 위치 입력받기
input_data = input()
row = int(input_data[1])
column = int(ord(input_data[0])) - int(ord('a')) + 1 # 아스키 코드 활용
# 나이트가 이동할 수 있는 8가지 방향 정의
steps = [(-2, -1), (-1, -2), (1, -2), (2, -1), (2, 1), (1, 2), (-1, 2), (-2, 1)]
# 8가지 방향에 대하여 각 위치로 이동이 가능한지 확인
result = 0
for step in steps:
# 이동하고자 하는 위치 확인
next_row = row + step[0]
next_column = column + step[1]
# 해당 위치로 이동이 가능하다면 카운트 증가
if next_row >= 1 and next_row <= 8 and next_column >= 1 and next_column <= 8:
result += 1
print(result)
알파벳 대문자와 숫자(0~9)로만 구성된 문자열이 입력으로 주어진다. 이때 모든 알파벳을 오름차순으로 정렬하여 이어서 출력한 뒤에, 그 뒤에 모든 숫자를 더한 값을 이어서 출력한다.
예를 들어 K1KA5CB7
이라는 값이 들어오면 ABCKK13
을 출력한다.
입력 조건 : 첫째 줄에 하나의 문자열 S
가 주어진다.
K1KA5CB7
ABCKK13
data = inpu()
result = []
value = 0
# 문자를 하나씩 확인하며
for x in data:
# 알파벳인 경우 결과 리스트에 삽입
if x.isalpha():
result.append(x)
# 숫자는 따로 더하기
else:
value += int(x)
# 알파벳을 오름차순으로 정렬
result.sort()
# 숫자가 하나라도 존재하는 경우 가장 뒤에 삽입
if value != 0:
result.append(str(value))
# 최종 결과 출력(리스트를 문자열로 변환하여 출력)
print(''.joint(result))