서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?
2. 문제 포인트
중복되지 않는 자연수 개수 구하기
반응형
3. 접근법
S를 자연수로 하나씩 빼면서 총 개수를 구한다
1, 2, 3... 숫자 하나씩을 S에서 빼면서 계산하다가 뺄 수(n)보다 S의 나머지가 작은 경우 반복문을 종료한다. ex. 15인 경우 15 - 1 - 2 - 3 - 4 - 5 = 0 >> 5번 17 - 1 - 2 - 3 - 4 - 7 = 0 >> 5번 - 1~5까지 빼면 17은 2가 남게 됨 - 1~4까지 빼고 7을 빼면 중복되지 않은 자연수들로 계산이 가능
4. 결과 코드
import sys
a = int(sys.stdin.readline().strip())
# 숫자 사용 횟수
cnt = 0
# 계산에 사용될 숫자
num = 1
while True:
# 입력받은 숫자에서 1부터 하나씩 빼서 숫자 사용 횟수 계산
a -= num
cnt += 1
num += 1
# 1부터 1씩 증가한 num이 a의 나머지값보다 크면 숫자가 중복되어 사용되기에
# num이 a보다 크게 되는 경우 루프 종료
if num > a:
break
print(cnt)
# 1789번 수들의 합
# https://www.acmicpc.net/problem/1789
다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모두 뒤집는 것이다. 뒤집는 것은 1을 0으로, 0을 1로 바꾸는 것을 의미한다.
예를 들어 S=0001100 일 때,
전체를 뒤집으면 1110011이 된다.
4번째 문자부터 5번째 문자까지 뒤집으면 1111111이 되어서 2번 만에 모두 같은 숫자로 만들 수 있다.
하지만, 처음부터 4번째 문자부터 5번째 문자까지 문자를 뒤집으면 한 번에 0000000이 되어서 1번 만에 모두 같은 숫자로 만들 수 있다.
문자열 S가 주어졌을 때, 다솜이가 해야하는 행동의 최소 횟수를 출력하시오.
2. 문제 포인트
0과 1로 이루어진 문자열 입력
모두 같은 숫자로 만들기 (0, 1 무관)
한번에 근접한 문자 같이 뒤집기 가능
반응형
3. 접근법
모든 숫자를 0으로 만들때와 1로 만들때를 구한 후 작은 값 출력
전체를 1을 만드는 뒤집기 횟수 == split("0")으로 리스트를 생성한 후 만든 요소의 개수
전체를 0을 만드는 뒤집기 횟수 == split("1")으로 리스트를 생성한 후 만든 요소의 개수
min()으로 두가지 경우 중 작은 값 출력
4. 결과 코드
import sys
a = sys.stdin.readline().strip()
# 1, 0을 기준으로 문자열을 나눠 리스트 만들기
## list comprehension을 이용하여 내용없는 요소는 제거
b = [bb for bb in a.split("1") if bb]
c = [cc for cc in a.split("0") if cc]
print(min(len(b), len(c)))
# 1439번 뒤집기
# https://www.acmicpc.net/problem/1439
2019년 올해도 어김없이 아주대학교 프로그래밍 경시대회(Ajou Programming Contest, APC)가 열렸다! 올해 새롭게 APC의 총감독을 맡게 된 준표는 대회 출제 과정 중 큰 고민에 빠졌다. APC에 참가하는 참가자들이 너무 다양해 대회 문제 난이도 설정이 너무 어렵기 때문이다.
APC는 프로그래밍 대회에 익숙하지 않은 학생들과 전공생이 아닌 학생들도 대거 참가하기 때문에 모두가 풀거나 도전할 수 있는 난이도 커브를 갖춰야 한다. 또한 '경인지역 6개대학 연합 프로그래밍 경시대회 shake!'에 참가할 학교 대표 10인을 선발하기 위한 대표 선발전으로서의 변별력도 갖추어야 하며, 외부인들이 따로 참가할 수 있는 Open Contest가 동시에 진행되기 때문에 소위 '고인물'들에게 한 시간도 안되어 대회가 정복당하는 일도 막고 싶다. 여기에 APC 출제진인 준표, 만영, 현정, 준서는 문제를 준비하는 데 무척 고생을 했기 때문에 참가자들이 모든 문제를 한번씩은 읽어주었으면 하는 소망도 가지고 있다.
욕심 그득한 준표는 고민끝에 이 수많은 니즈를 충족시키기 위한 한가지 해결책을 제안했다. 하나의 문제를 제한조건을 통해 쉬운 버전과 어려운 버전으로 나누어 쉬운 버전만 맞더라도 부분점수를 주는 서브태스크 문제로 대회를 구성하는 것이다. 또한 이렇게 만들어진 문제를쉬운 버전의 난이도순으로 배치하려 한다.
위와 같이 문제를 준비하면 프로그래밍 대회에 익숙하지 않은 사람은 앞에서부터 따라가면서 도전해볼 수 있어 쉬운 문제를 찾는 데 시간을 쓰지 않을 수 있고, 어려운 버전으로 학교 대표 선발을 위한 변별력을 유지할 수 있으며, 모든 문제가 읽히길 바라는 출제진의 소망도 이룰 수 있을 것이다!
<그림1> 출제중 평가한 문제들의 난이도 예시 (예제2)
<!-- 아래 이야기는 팩션입니다. -->
현정이는 APC에 한 번이라도 나가보고 싶다는 소망이 있다. 하지만 이 소망은 여태까지 단 한 번도, 그리고 앞으로도 이루어질 리 없기 때문에 현정이가 입버릇처럼 하게 된 말이 있는데...
현정 : 아~~ 나도 APC 참가만 했으면 상금 받는 건데~~~~~
준표 : ... 그건 아닌 것 같은데?
현정이의 근거 없는 자신감이 눈꼴신 준표는 출제 중에 평가한 문제 난이도를 통해 현정이의 예상 점수를 알려주고 현정이가 현실을 받아들일 수 있도록 도와주고자 한다.
현정이는L 만큼의 역량을 가지고 있어 L보다 작거나 같은 난이도의 문제를 풀 수 있다. 또한 현정이는 코딩이 느리기 때문에 대회 시간이 부족해K개보다 많은 문제는 해결할 수 없다. 어떤 문제에 대해 쉬운 버전을 해결한다면 100점을 얻고, 어려운 버전을 해결한다면 여기에 40점을 더 받아 140점을 얻게 된다. 어려운 버전을 해결하면 쉬운 버전도 같이 풀리게 되므로, 한 문제를 해결한 것으로 계산한다.
현정이가 APC에 참가했다면 최대 몇점을 얻을 수 있었을지 알려주자.
2. 문제 포인트
1행에 "문제 개수, 역량, 풀이 가능한 문제 수" 를 입력 받음
2행부터는 쉬운버전 난이도 + 어려운 버전 난이도를 입력 받음
현정이가 받을 수 있는 최고 점수를 계산
반응형
3. 접근법
어려운 난이도까지 풀 수있는 문제(140점 짜리)를 먼저 푼다 - 어려운문제까지 풀어도 문제 풀이 시간은 1로 계산된다 - 다시말해 입력을 받을때마다 점수를 계산하면 최대값을 얻을 수 없다
ex. 풀수 있는 문제 수(K) < 풀 수 있는 140점 문제 수 - 위와 같은 경우 140 * K점수가 최대 점수가 된다
4. 결과 코드
import sys
a = list(map(int, sys.stdin.readline().split()))
sub = 0
basic = 0
# 문제수(a[0])만큼 반복
for _ in range(a[0]):
b = list(map(int, sys.stdin.readline().split()))
# 전체 문제 중 어려운버전까지 풀 수 있는 문제 수 계산
# 최종 합계에 점수를 더해버리면 안된다.
if a[1] >= b[1]:
sub += 1
# 전체 문제 중 쉬운 버전만 풀 수 있는 문제 수 계산
elif a[1] >= b[0]:
basic += 1
# 어려운 문제를 푼 수를 점수로 환산
# '풀 수 있는 문제 수' vs '풀이 가능한 총 문제 수'중 작은 값 선택
## ex. 3문제 풀이 가능 시간, 5개의 어려운 문제 풀이 가능 능력인 경우 어려운 문제 3개만 풀이가 가능(시간 제한)
score = 140 * min(sub, a[2])
# 위에서 어려운 문제를 다 푼뒤 더 풀 시간이 있는 경우 쉬운 문제 풀이
## 풀이 가능 숫자 * 100점을 계산
if a[2] - sub > 0:
score += 100 * min(basic, (a[2] - sub))
print(score)
# https://www.acmicpc.net/problem/17224
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
2. 문제 포인트
거스름돈 종류 (500엔, 100엔, 50엔, 10엔, 5엔, 1엔)
잔돈 개수의 최소값
반응형
3. 접근법
큰 금액 동전을 최대한 많이 사용하면 되는 문제
1엔짜리까지 있기에 단순하게 계산 가능 (1엔짜리가 없을 경우 잔돈의 1의 자리가 5나 0으로 끝나지 않으면 계산 불가)
4. 결과 코드
import sys
a = int(sys.stdin.readline())
# 잔돈 금액 계산
chg = 1000 - a
# 동전 단위 리스트 (큰 동전부터 내림차순)
coin = [500, 100, 50, 10, 5, 1]
# 동전 개수
coin_cnt = 0
# coin에 들어있는 동전 단위별로 반복
for n in coin:
# n값으로 나눠지면 계산
if chg // n > 0:
# 코인 개수 추가
coin_cnt += chg // n
# 현재 단위 제외 후나머지 잔액 계산
chg -= n * (chg // n)
# 결과값 출력
print(coin_cnt)
# 5585번 거스름돈
# https://www.acmicpc.net/problem/5585
강산이네 동네에 드디어 극장이 생겼고, 강산이는 극장에 놀러갔다. 매점에서 콜라를 산 뒤, 자리에 앉은 강산이는 큰 혼란에 빠졌다. 양쪽 컵홀더를 이미 옆 사람들이 차지했기 때문에 콜라를 꽂을 컵 홀더가 없었기 때문이다. 영화를 보는 내내 콜라를 손에 들고 있던 강산이는 극장에 다시 왔을 때는 꼭 콜라를 컵 홀더에 놓겠다는 다짐을 한 후 집에 돌아갔다.
극장의 한 줄에는 자리가 N개가 있다. 서로 인접한 좌석 사이에는 컵홀더가 하나씩 있고, 양 끝 좌석에는 컵홀더가 하나씩 더 있다. 또, 이 극장에는 커플석이 있다. 커플석 사이에는 컵홀더가 없다.
극장의 한 줄의 정보가 주어진다. 이때, 이 줄에 사람들이 모두 앉았을 때, 컵홀더에 컵을 꽂을 수 있는 최대 사람의 수를 구하는 프로그램을 작성하시오. 모든 사람은 컵을 한 개만 들고 있고, 자신의 좌석의 양 옆에 있는 컵홀더에만 컵을 꽂을 수 있다.
S는 일반 좌석, L은 커플석을 의미하며, L은 항상 두개씩 쌍으로 주어진다.
어떤 좌석의 배치가 SLLLLSSLL일때, 컵홀더를 *로 표시하면 아래와 같다.
*S*LL*LL*S*S*LL*
위의 예에서 적어도 두 명은 컵홀더를 사용할 수 없다.
2. 문제 포인트
좌석 종류 2가지 (S석(일반석) L석(커플석))
컵홀더는 좌석 사이와 양단 끝에 위치
최대 컵홀더 사용 가능 인원 수 구하기
반응형
3. 접근법
S는 한글자지만 L은 LL두 글자로 표시됨
방법 2가지
L이 두번 반복되는것을 확인 후 L두번당 한번씩 컵 홀더 위치 시키기
LL을 다른 문자 (ex. C)로 치환하여 풀이
4. 결과 코드_1 (LL의 반복을 확인하여 컵홀더 위치시키기)
import sys
a = int(sys.stdin.readline())
b = sys.stdin.readline()
# 시작점 컵홀더 하나 추가
result = "*"
# 각 자리별 컵홀더 자리 *로 표시
## L이 두번 나오는지 검출하는 방법
for n in b:
# "S"가 나오면 바로 옆에 컵홀더 위치
if n == "S":
result += n + "*"
# 커플석인 L이 나오면 두번 중복되어 나왔는지 확인하여 *추가
if n == "L":
if result[-1] == "L":
result += "L" + "*"
else:
result += "L"
# 결과값 출력
## 일반 좌석만 존재하는 경우 컵홀더 숫자가 좌석수(사람수)보다 1개 많아지는 예외 발생
## min으로 컵홀더 사용 개수가 사람수를 넘어가지 않도록 처리
print(min(result.count("*"), a))
# https://www.acmicpc.net/problem/2810
4. 결과 코드_2 (LL 치환을 이용)
import sys
a = int(sys.stdin.readline())
b = sys.stdin.readline().strip()
# LL(커플석)을 하나의 문자로 치환
b = b.replace("LL", "C")
# 컵홀더 수와 사람수를 비교하여 적은 수 출력
print(min(len(b)+1, a))
# https://www.acmicpc.net/problem/2810
상근이가 숫자 5를 볼 때, 5로 볼 때도 있지만, 6으로 잘못 볼 수도 있고, 6을 볼 때는, 6으로 볼 때도 있지만, 5로 잘못 볼 수도 있다.
두 수 A와 B가 주어졌을 때, 상근이는 이 두 수를 더하려고 한다. 이때, 상근이가 구할 수 있는 두 수의 가능한 합 중, 최솟값과 최댓값을 구해 출력하는 프로그램을 작성하시오.
2. 문제 포인트
5를 6으로, 6을 5로 바꿔 쓸 수 있다
최대값과 최솟값을 구하라
반응형
3. 접근법
최대값 구하기 = 모든 5를 6으로 바꿔서 합계 출력
최솟값 구하기 = 모든 6을 5로 바꿔서 합계 출력
4. 결과 코드
import sys
a = sys.stdin.readline().strip()
# 입력받은 두 수의 최솟값, 최대값 만들기
## 모든 6을 5로 만들면 최솟값
temp = ""
for num in a:
if num == "6":
num = "5"
temp += num
min_val = list(map(int, temp.split(" ")))
## 모든 5를 6으로 만들면 최대값
temp = ""
for num in a:
if num == "5":
num = "6"
temp += num
max_val = list(map(int, temp.split(" ")))
# 결과 출력
print(f"{sum(min_val)} {sum(max_val)}")
## https://www.acmicpc.net/problem/2864
메이플스토리에는 전문 기술이라는 제작 시스템이 있다. 전문 기술은 특정량의 피로도가 쌓이는 대신 다양한 장비 및 비약을 제작할 수 있는 시스템이다. 장신구 명장인 임스는 어떻게 하면 더 효율적으로 많은 장신구를 제작할 수 있을지 고민에 빠졌다.
임스가 만들 수 있는 장신구는 N개가 있고, 각각의 장신구를 만들면A만큼의 피로도가 누적된다.
피로도가 200 미만인 경우, 장신구를 제작할 수 있다. 현재 쌓인 피로도가 P일 때, 임스가 제작할 수 있는 장신구의 최대 개수를 구해보자!
2. 문제 포인트
만들 수 있는 개수 한정 (N)
각 장신구마다 A만큼의 피로도 누적
피로도가 200미만이면 제작 가능 199일때 피로도 100이 누적되는 장신구도 제작 가능 시작 시점에서 200미만이면 됨
최대 개수 구하기
반응형
3. 접근법
가장 최대 제작 개수가 중요 (피로도에 따른 가중치 없음) 입력 받은 장신구별 피로도 증가량을 오름차순으로 정렬 후 사용
4. 결과 코드
import sys
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
# 각 아이템별 소모 피로도를 오름차순 정리
b = sorted(b)
cnt = 0
# 전체 횟수 a[1]만큼 반복
## 제한 없이 while True문을 사용할 경우 예외 발생
## ex. 10피로도 2개 아이템 (1, 2)
for n in range(a[1]):
# 현재 피로도가 200이상인지 확인하여 True인 경우 for문 종료
if a[0] >= 200:
break
# a[0](현재피로도)에 가장 작은 b값 순차적으로 덧셈
a[0] = a[0] + b[cnt]
cnt += 1
print(cnt)
# https://www.acmicpc.net/problem/25496
