1이 될 때까지
문제
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 합니다. 단, 두 번째 연산은 K로 나누어 떨어질 때만 선택할 수 있습니다.
- N에서 1을 뺍니다.
- N을 K로 나눕니다.
N과 K가 주어질 때 N이 1이 될때까지 1번 혹은 2번의 과정을 수행하는 최소 횟수를 구하는 프로그램을 작성하세요.
입력 조건- 첫째 줄에서 N(1 <= N <=100,000)과 K(2 <= K <= 100,000)가 공백을 기준으로 하여 각각 자연수로 주어집니다.
- 예시 : 25 5
출력 조건- 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번의 과정을 수행해야 하는 횟수의 최솟값을 출력합니다
- 예시 : 2
- 첫번째 풀이
# n과 k에 입력 값을 받기 위한 변수
n, k = map(int, input().split())
# 횟수를 저장할 변수
result = 0
# 몫과 나머지를 저장할 변수
share = 0
rest = 0
share = n // k
rest = n % k
# n이 k로 나눠질 경우
if share > 0:
result = share + rest
print(result)
# n이 k로 나눠지지 않을 경우
else:
print(rest)위 코드는 실제 풀이가 아닌 풀이를 보기 전 저의 코드입니다.
처음 "단, 두 번째 연산은 K로 나누어 떨어질 때만 선택할 수 있습니다."라는 구문을 고려하지 않고 if문 없이 코딩하였습니다.
하지만 위 구문을 고려해 if문 추가해 주었고, 해당 코드의 시간복잡도는
O(상수)가 될 것입니다.
- 두번째 풀이
# N, K공백을 기준으로 구분하여 입력 받기
n, k = map(int, input().split())
result = 0
while True:
# N이 K로 나누어 떨어지는 수가 될 때까지만 1씩 빼기
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)위 코드는 풀이로 나온 코드이다.
whlie문을 통해 문제를 풀었습니다.
마지막에서 2번째 줄은 ★에서 나눌 수 없지만 result에 1을 더하기 때문에
result += (n-1)이라는 코드를 넣어주었습니다.
N이 엄청 큰 수일 경우에도 빠르게 처리하려면 N과 가장 가까운 K의 배수를 찾아 그 차를 구하여
결과에 더하고, 이후 나누는 작업을 계속 진행한다.
이는 1을 빼는 연산을 한번에 구해서 result에 더해주는 과정이 된다.
해당 코드의 시간복잡도는 O(n)입니다.
문제점
위 코드를 보는 순간 저는 문제를 잘못 이해하고 있었다고 깨닳았습니다.
저의 풀이는 몇 번을 나누고 몇 번을 뺏는지 count하는 문제로 생각했습니다...😥
이후 풀이 코드를 보고도 result에 1을 빼주는 이유도 찾기 힘들었습니다.
때문에 코드가 아예 다른 방향으로 풀이되었고, 풀이코드마저 이해하지 못 했습니다.
좀 더 공부해 보겠습니다!!
곱하기 혹은 더하기
문제
각 자리가 숫자 0~9로만 이루어진 문자열이 주어졌을 때, 왼쪽부터 오른쪽으로 하나씩 모든 숫자를 확인하며 숫자 사이에 곱하고 혹은 더하기 연산자를 넣어 결과적으로 만들어질 수 있는 큰수를 구하는 프로그램을 작성하세요
단, 곱하기를 더하기보다 먼저 계산하는 기존 방식과 달리 모든 연산은 왼쪽부터 순서대로 이루어진다고 가정합니다.
입력 조건
- 첫째 줄에 여러 개의 숫자로 구성된 하나의 문자열 S가 존재 (1 <= S <= 20)
- 예시 : 02984
출력 조건- 첫째 줄에 만들어질 수 있는 가장 큰 수를 출력.
- 예시 : 576
- 풀이
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)수행하는 과정에서 0과 1일 경우 더해주고 나머지 숫자는 곱하기를 해준다.
이때 index[0]번째는 연산에서 맨 앞에 수 이므로 result에 넣어준다.
모험가 길드
문제
한 마음에 모험가가 N명 있다. 모험가 길드에서는 N명의 모험가를 대상으로 '공포도'를 측정했는데, '공포도'가 높은 모험가는 쉽게 공포를 느껴 위험 상황에서 제대로 대처할 능력이 떨어진다.
모험가 길드장인 개구리가 모험가 그룹을 안전하게 구성하고자 공포도가 X인 모함가는 반드시 X명 이상으로 구성한 모험가 그룹에 참여해야 여행을 떠날 수 있도록 규정했다.
개구리가 최대 몇 개의 모험가 그룹을 만들수 있는지 구하는 프로그램을 작성하라.
입력 조건
- 첫째 줄에 모험가의 수 N이 주어진다. (1 <= N <= 100,000)
- 둘째 줄에 각 모험가의 공포도의 값을 N이하의 자연수로 주어지며, 각 자연수는 공백으로 구분
- 예시 : 5
2 3 1 2 2
출력 조건- 여행을 떠날 수 있는 그룹 수의 최댓값을 출력.
- 예시 : 2
- 풀이
n = 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) # 총 그룹의 수 출력위 코드에서는 최댓값을 출력해주기 위해 각 모험가의 공포도를 오름차순으로 정렬하였다.
이를 통해 탐욕법을 사용할 수 있는데, for loop를 통해 모험가의 공포도를 하나씩 if문을 통해 그룹 형성 여부를 판단하고 있다. 만약에 그룹이 형성되면 그룹의 수를 1 증가 시키고, 그렇지 않다면 오름차순으로 정렬된 다음 공포도를 확인한다.
