위 링크에서 첫번째 순서인 그리디 알고리즘 문제를 풀고 풀이를 기록하는 게시글입니다.
1. 그리디 알고리즘
- 그리디(Greedy) : 욕심많은,탐욕스러운
- 미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법.
- 각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘
- 현재 상황에서 '지금 당장 좋은 것!'만 고르는 것.
- 문제를 풀기위한 최소한의 아이디어를 적절히 떠올려야 풀 수 있다.
- 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘입니다. 동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념.
- 문제를 읽고 문제가 해결될 수 있는 경우의 수를 모두 생각해볼 것.
문제
(❌ 표시는 혼자 못푼 문제)
2023. 9. 26 2일차
1. 1343번 폴리오미노 (실버5) 문제링크
문제 해석
. X 로 이루어진 보드판이 주어진다.
문자열 AAAA, BB 두 개를 무한개 가지고 있다.
문자열 두개로 보드판의 X를 다 덮어야한다.
.은 덮으면 안된다.
입력
보드판, 보드판의 크기는 최대 50
출력
사전 순으로 가장 앞서는 답을 출력. 만약 덮을 수 없으면 -1을 출력
(사전 순으로 가장 앞서는 답을 출력해야하기 때문에 앞에서 부터 4칸이 존재하면 AAAA를 제일 먼저 넣는다고 생각하고 문제를 풀어야한다.)
내 코드
def getStr(n): #X개수에 따라 넣을 수 있는 답이 정해져있기 때문에 규칙을 적용하였다.
# n = 6 일 경우
# 3 = 6//2
# 3/2 만큼 AAAA를 3%2만큼 BB를 붙인다.
n = n//2
return n//2 * 'AAAA' + n%2 *'BB'
board = input()
result = ''
count = 0
for i in board:
#연속된 X의 개수를 센다.
if i == 'X':
count+=1
else:
#홀수개의 X는 채울 수 없다. -1 출력을 위해 반복문 탈출
if count%2!=0:
break
result += getStr(count)
result += '.'
count = 0
if count%2!=0:
print(-1)
else:
result += getStr(count)
print(result)다른 사람 코드
board = input()
board = board.replace("XXXX", "AAAA")
board = board.replace("XX", "BB")
#XXXX와 XX는 모두 사라졌을 것이고
#X가 남아있다면 -1을, X가 없다면 바뀐 board를 출력
if 'X' in board:
print(-1)
else:
print(board)이 문제의 포인트
- 제일 앞에서 AAAA부터 채워나가면돼서 그리디인가?
- 문자열의 replace함수는 왼쪽부터 해당하는 문자열을 찾아서 치환한다.
- 요소가 있는지 확인하기위해서는 if 'X' in 그룹형자료형을 사용하면된다.
2023. 9. 27 3일차
2. 14916번 거스름돈 (실버5) 문제링크
문제 해석
2원짜리, 5원짜리로만 거스름돈을 준다.
동전의 개수가 최소가 되도록 거슬러준다.
거스름돈이 n인 경우, 최소 동전의 개수가 몇 개인지를 알려주는 프로그램을 만들어라.
제한: 2초 512MB
입력
첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다.
출력
거스름돈 동전의 최소 개수를 출력한다. 만약 거슬러 줄 수 없으면 -1을 출력한다.사전 순으로 가장 앞서는 답을 출력. 만약 덮을 수 없으면 -1을 출력
내 코드
거스름돈에서 걸러줄 수 있는 최대 5원의 개수에서 하나씩 줄여가면서
5원을 거스르고 남은돈을 2원으로 거슬러줄 수 있는지 확인한다.
5원을 0개까지 고려해야한다. range(5원최대개수,-1,-1)
def fun(n):
#거스름돈에서 걸러줄수있는 최대 5원의 개수를 구한다.
max5count = n//5
for i in range(max5count,-1,-1):
val = n-5*i
#5원을 채우고 남은 돈을 2원으로 채울 수 있는지 5원의 개수를 줄이면서 확인한다.
if val%2==0:
return i+val//2
return -1
n = int(input())
print(fun(n))2023. 9. 28 4일차
3. 2828번 사과담기게임 (실버5) 문제링크
문제 해석
위에서 사과가 내려오는 세로 N칸 스크린이 있고, 스크린 아래에 M칸을 차지하는 바구니가 있다. (M<N)
바구니로 내려오는 사과를 담는 게임이다.
가장 처음에 바구니는 제일 왼쪽 부터 시작해서 M칸을 차지한다.
사과가 N칸 중 한칸의 상단에서 직선으로 떨어진다.
떨어지는 사과를 바구니로 모두 담으려고한다. 바구니 이동 거리의 최솟값을 구하여라.
바구니는 스크린을 넘어가면 안된다.
제한: 1초 128MB
입력
첫째 줄에 N과 M이 주어진다. (1 ≤ M < N ≤ 10) 둘째 줄에 떨어지는 사과의 개수 J가 주어진다. (1 ≤ J ≤ 20) 다음 J개 줄에는 사과가 떨어지는 위치가 순서대로 주어진다.
출력
모든 사과를 담기 위해서 바구니가 이동해야 하는 거리의 최솟값을 출력한다.
내 코드
사과가 바구니의 바깥에있으면 사과와 가까운 바구니의 끝부분이 사과를 받도록 이동한다.
N, M = map(int, input().split())
#바구니의 시작위치
start = 1
#바구니의 끝위치
end = (start-1) + M
#바구니가 이동한 거리
move = 0
count = int(input())
for _ in range(count):
i = int(input())
if start > i:
move += (start - i)
start = i
end = (start-1) + M
elif end < i:
move += (i - end)
end = i
start = (end+1)-M
print(move)2023. 9. 29 5일차
4. 2217번 로프(실버4) 문제링크
문제 해석
물체를 들어올릴 수 있는 로프가 있다. N개. (1<= N <= 100,000)
로프는 들어올릴 수 있는 중량이 서로 다를 수 있다.
여러개(k개)의 로프로 w중량인 물체를 들어올릴 때 각각의 로프에는 고르게 w/k 만큼의 중량이 걸리게 된다.
각 로프의 정보가 주어졌을 때, 로프를 이용하여 들어올릴 수 있는 물체의 최대 중량을 구하여라.
모든 로프를 사용할 필요는 없다. 몇개의 로프를 골라 사용해도된다.
제한: 2초, 192MB
입력
첫째 줄에 정수 N이 주어진다. 다음 N개의 줄에는 각 로프가 버틸 수 있는 최대 중량이 주어진다. 이 값은 10,000을 넘지 않는 자연수이다.
출력
첫째 줄에 답을 출력한다.
내 코드
고른 로프에 걸리는 중량은 그 중 최소값과 같은 중량이 모든 로프에 걸리게 된다.
오름차순 정렬후, 최소값 루프를 순차적으로 고른다.
고른 최소값 루프보다 큰 루프들까지 다 고른다.
(최소값 루프 * 최소값 루프 이후 루프 개수 = 최소값 루프를 골랐을 때 가장 많이 들어올릴 수 있는 중량) 식으로 최대 중량을 구한다.
N = int(input())
arr = []
for _ in range(N):
arr.append(int(input()))
#로프중량 오름차순으로 정렬
arr.sort()
arrLen = len(arr) #(참고)N이랑 동일한 값임 arrLen말고 N으로 사용했어도 됐었음
maxWeight = 0
for i,value in enumerate(arr):
#최소값부터 최소값보다 큰애들 개수를 구한다.
ropeNum = arrLen - i
#최소값 이후 로프들은 최소값 중량만큼 들 수 있으므로
#최소값을 로프 개수에 곱한다. 이 값이 현재 최소값 로프에 대한 최대 중량이다.
weight = value * ropeNum
if maxWeight < weight:
maxWeight = weight
print(maxWeight)다른 사람 코드
문제를 푸는 방식은 같았지만 입력할 때 사용한 방식과 정렬에 사용한 라이브러리가 달랐다.
나는 input()을 썼고 이 분은 sys.stdin.readline().rstrip()을 사용하셨다.
속도차이는 거의 30배.....
input() : 3964ms
sys.stdin.readline().rstrip() : 116 ms
input()을 사용했어도 문제의 제한 시간은 통과하긴하지만 어마어마한 속도차이를 보고 이제부터는 readline()써야겠다 싶다.
이 분 코드를 보니 sys.stdin.readline().rstrip()을 일일이 적기힘드니 input()함수로 만들어서 사용을 하셨다. 나도 함수 만들어두고 input()으로 사용해야겠다. 함수를 input()으로 만들어놓으면 시스템의 input()을 사용하는게 아니라 내가 만들어놓은 함수를 사용하게된다.
나는 정렬에 arr.sort()를 사용해서 자체적으로 정렬되도록했는데 이 코드에서는 sortedlist = sorted(arr) 방식으로 정렬된 리스트를 반환하도록 했다. 백준으로 돌려본 결과 sorted(arr)가 속도가 4ms 더 빨랐다. 아주 경미한 차이이지만 sorted(arr)를 써야겠다. 더 나은거 쓰는게 좋으니까
import sys
#입력을 많이 받기 때문에 readline()을 실행해주는 input()함수를 정의해두고 쓰자
def input():
return sys.stdin.readline().rstrip()
N = int(input())
rope = sorted([int(input()) for _ in range(N)]) # 한줄한줄 입력받아서 리스트화할 때 이렇게 사용하기
res = 0
for _ in range(N): # for문에 _ 는 변수로 사용할 수 있다고 한다.
temp = (N-_) * rope[_]
if temp > res:
res = temp
print(res)이 문제의 포인트
- 한줄 한줄 숫자 입력받은 값을 정렬할 때
sortedList = sorted([int(input()) for _ in range(N)]- 입력값이 많을 때 input()함수 만들어서 readline()으로 입력받기
import sys
def input():
return sys.stdin.readline().rstrip()- for문에 _를 변수로 사용할 수 있음
for _ in range(N):
print(_)2023. 9. 30 6일차 (1)
❌ 5. 13305번 주유소 (실버4) 문제링크
문제 해석
N개의 도시가 일직선 도로 위에 있다.
제일 왼쪽 도시에서 제일 오른쪽의 도시로 자동차가 이동한다.
인접한 두 도시 사이의 길이가 서로 다를 수 있다. (km단위)
각 도시에 하나의 주유소가 있다.
제일 왼쪽 주유소에서 기름을 넣고 출발해야한다.
1km마다 1리터의 기름을 사용한다.
주유소마다 리터당 가격은 다를 수 있다.
제일 왼쪽 도시에서 제일 오른쪽 도시로 이동하는 최소의 비용을 계산하는 프로그램을 만들어라.
제한: 2초 512MB
입력
표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1개의 자연수로 주어진다. 다음 줄에는 주유소의 리터당 가격이 제일 왼쪽 도시부터 순서대로 N개의 자연수로 주어진다. 제일 왼쪽 도시부터 제일 오른쪽 도시까지의 거리는 1이상 1,000,000,000 이하의 자연수이다. 리터당 가격은 1 이상 1,000,000,000 이하의 자연수이다.
출력
표준 출력으로 제일 왼쪽 도시에서 제일 오른쪽 도시로 가는 최소 비용을 출력한다.
(오늘은 직접 풀지못해서 풀이를 참고해서 풀었다.)
다른 사람 코드
다음구간의 거리를 가기위해서 현재의 주유소와 지나온 주유소의 리터당 가격중 가장 작은 값으로 도로를 이동한다.
N = int(input())
roads = list(map(int, input().split())) #도시 사이거리
costs = list(map(int, input().split())) #주유소리터당 가격
res = 0
m = costs[0]
for i in range(N-1):
if m > costs[i]:
m = costs[i]
res += m * roads[i]
print(res)다른 사람 코드 참고한 내 코드
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
roads = list(map(int, input().split())) #도시 사이거리
costs = list(map(int, input().split())) #주유소리터당 가격
result = 0
lowestCost = costs[0]
for i in range(N-1):
if lowestCost > costs[i]:
lowestCost = costs[i]
result += lowestCost * roads[i]
print(result)
이 문제의 포인트
- 그리드 알고리즘 문제 이므로 그때그때 최적의 값을 찾는 단순한 방법을 생각해야한다.
- 자동차가 도시를 거치면서 최적의 값을 찾는 방법을 찾아내지 못하고 한번에 모든 경우의 비용을 구하여 비교해서 구하려고 했다. 바보같이 ㅠㅠㅠㅠ
2023. 9. 30 6일차 (2)
6. 1758번 알바생 강호 (실버4) 문제링크
문제 해석
8시부터 오픈하는 스타박스. 8시에 줄서있는 손님에게 커피를 준다.
손님들은 커피를 몇번째에 받는지에 다라 팁을 다른 액수로 강호에게 준다.
각 손님이 강호에게 팁으로 원래 주려고 생각했던 돈 - (받은 등수 -1) 만큼의 팁을 강호에게 준다.
위의 식으로 나온 값이 음수라면 강호는 팁을 받을 수 없다.
손님의 순서를 적절히 바꿨을 때, 강호가 받을 수 있는 팁의 최댓값을 구하는 프로그램을 작성하시오.
제한: 2초 256MB
입력
첫째 줄에 스타박스 앞에 서 있는 사람의 수 N이 주어진다. N은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 총 N개의 줄에 각 사람이 주려고 하는 팁이 주어진다. 팁은 100,000보다 작거나 같은 자연수이다.
출력
강호가 받을 수 있는 팁의 최댓값을 출력한다.
내 코드
어차피 음수가 되면 못받는 팁이므로 팁계산에서 더 큰 음수가 나오는게 낫다.
따라서, 제일 팁을 많이 주는 사람 순서대로 세울 수 있도록 한다.
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = sorted([int(input()) for _ in range(N)], reverse=True)
tip = 0
for i in range(N):
tmp = arr[i] - i
if tmp > 0 :
tip += tmp
print(tip)2023. 10. 1 7일차 (1)
7. 11508번 2+1 세일 (실버4) 문제링크
문제 해석
유제품 2+1 하는 행사
유제품을 3개에 그 중 가장 싼 것은 무료. 나머지 두개 가격만 지불
한번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불
N팩의 유제품을 최소 비용으로 구매해보자.
제한: 1초 64MB
입력
첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.
두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.
출력
재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 231-1보다 작거나 같다.
(C였으면 long자료형으로 사용해야하는 문제였던 것 같다.)
내 코드
최대한 큰 가격이 3개 묶음에서 가장 작은 값이어야 한다.
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = sorted([int(input()) for _ in range(N)], reverse=True)
res = 0
for _ in range(N):
if (_+1) % 3 ==0:
continue
res += arr[_]
print(res)
# 36284kb 112ms2023. 10. 1 7일차 (2)
8. 11399번 2+1 세일 (실버4) 문제링크
문제 해석
ATM 1대에 N명의 사람들이 줄을 서 있다.
i번 사람이 돈을 인출하는 데 걸리는 시간은 Pi분
줄서는 순서에 따라서 , 돈을 인출하는데 필요한 시간의 합이 달라진다.
각 사람이 ATM을 사용하는 시간이 주어진다.
(앞 사람이 돈을 인출하는데 걸리는 시간 + 현재 사람이 돈을 인출하는 데 필요한 시간 )이 전체 기다리는 시간이다.
각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하여라
제한: 1초 256MB
입력
첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)
출력
첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.
내 코드
(앞사람이 기다리는 시간 + 내가 기다리는 시간) 이 최소가 되어야 하니까 앞에 있는 사람들이 시간이 적은 사람들이어야한다. (오름차순정렬)
전체 각각의 사람이 ATM을 사용하는 시간을 합하고 뒷사람이 기다리는 시간을 하나씩 빼면서 전체 사람이 기다리는 시간을 구한다.
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = sorted(list(map(int, input().split())))
res = 0
#전체 각각의 사람이 ATM을 사용하는 시간을 합한다.
time = sum(arr)
for i in range(N-1, -1,-1):
#뒷사람이 기다리는 시간을 하나씩 빼면서 전체 사람이 기다리는 시간을 구한다.
res += time
time -= arr[i]
print(res)
# 31256kb 44ms2023. 10. 2 8일차
9. 11047번 동전 0 (실버4) 문제링크
문제 해석
동전 N종류가 있다. 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 k로 만들려고 한다.
이 때 필요한 동전의 개수의 최솟값을 구하여라.
제한: 1초 256MB
입력
첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)
출력
첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.
아이디어
거스름돈 문제라고 생각하자. k만큼의 거스름돈을 주어진 동전으로 거슬러 줘야하는 것이다.
가장 큰 동전으로 거슬러줄 수 있는 만큼 거슬러주고, 그 다음 큰 숫자만큼 거슬러주면 되는 것이다.
가장 큰 동전부터 거슬러주는 것이 최적의 해인 이유는?
A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수라는 조건이 있기 때문이다.
가지고 있는 동전 중, 가장 큰 단위가 항상 작은 단위의 배수이므로 "작은 단위의 동전들을 조합해 다른 해가 나올 수 없다."
만약, 800원을 거슬러줘야하는 상황에서 동전 단위가 배수가 아닌 수가 낀 경우라면.
[500, 400, 100] 이라면
그리디 알고리즘을 통해 푼다면 가장 큰 금액부터 나눠져서
500원 1개 , 100원 4개가 해일 것이다.
하지만 실질적으로 400원 두개가 최적의 해이다.
이 경우라면 그리디 알고리즘을 사용해 풀지 못하고, 전체 경우를 다따져 봐야할 것이다.
그리디 알고리즘은 이런 문제가 발생하기 쉽다.
따라서 그리디 알고리즘에서는 정당성 검토가 중요하다.
내 코드
큰 수 부터 총 금액에서 빼면서 내려간다.
import sys
def input():
return sys.stdin.readline().rstrip()
N, value = map(int,input().split())
arr = [int(input()) for _ in range(N)]
res = 0
for coin in reversed(arr):
if value ==0:
break
#가장 큰 동전으로 거슬러줄 수 있는 최대 동전의 개수가 0이상이면 최대 동전으로 거슬러준다.
if value // coin > 0:
res += value // coin
value -= (count * coin) #가장 큰 동전의 값을 뺀 나머지
print(res)
다른 사람 코드
비교 1.
'내 코드'에서는 해당 동전으로 개수를 카운팅할 수 있을 때만 계산할 수 있도록 했다. if value//i > 0
'다른 사람 코드'에서는 if 조건문을 사용하지 않고 모든 경우에서 계산을 해주는 것을 볼 수 있었다.
value // i 값이 0 이면 어차피 계산해줘도 for문 속 식에 영향을 안주기 때문.
% 연산이 한 줄 더 발생하지만 코드는 간결해진다.
그러나 연산이 더 늘어난다는 관점에서는 if 를 사용하는 것이 맞는 것 같다.
비교 2.
전체 값에서 큰 동전을 빼주고 남은 나머지를 구하기 위해
'내코드'에서는 남은 동전 = 남은 동전 - (큰동전 * 큰동전 개수) 식으로 계산했었는데
'다른 사람 코드'에서는 남은 동전 = 남은동전 % 큰동전 으로 하면 되는 식이었다.
import sys
def input():
return sys.stdin.readline().rstrip()
N, K = map(int,input().split())
coin_lst = [int(input()) for _ in range(N)]
count = 0
for coin in reversed(coin_lst):
count += K // coin_lst[i] #카운트 값에 K를 동전으로 나눈 몫을 더해줌
value %= coin_lst[i] # K는 동전으로 나눈 나머지로 계속 반복
print(res)이 문제의 포인트
- if 조건문을 사용하지 않아도 되는 경우인지 확인하기
- 특정 값에 a를 나눠서 나온 몫만큼의 a를 빼기 위해서는 mod 연산을 해준다. 이를 value -=value // a 로 썼지만 다음에는 value %=a로 바로쓸 수 있도록 하기
몫 = value // a
value %= a # value = value - (value //a)
문제에서 'A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수' 조건을 이해하게 해준 게시글
2023. 10. 3 9일차 (1)
10. 20115번 에너지 드링크 (실버3) 문제링크
문제 해석
N개의 에너지드링크를 한 데 합쳐서 하나의 에너지 드링크로 만들어 마시려고 한다.
서로 다른 두 에너지 드링크를 골라서 하나에 또 다른 하나를 붓는다. 이 때 붓는 쪽에서는 반을 흘려 양의 반만 추가된다.
에너지드링크가 하나만 남을 때까지 반복한다.
이렇게 합쳐서 만들 수 있는 에너지 드링크 최대양은?
제한: 1초 256MB
입력
첫째 줄에 페인이 가지고 있는 에너지 드링크의 수 N이 주어진다. (2 ≤ N ≤ 105)
둘째 줄에 각 에너지 드링크의 양이 공백으로 구분되어 주어진다. i번째 정수 xi (1 ≤ xi ≤ 109)는 에너지 드링크 i의 양이 xi임을 의미한다.
출력
첫째 줄에 페인이 최대로 만들 수 있는 에너지 드링크의 양을 출력한다.
절대/상대 오차는 10^-5까지 허용한다.
내 코드
가장 큰 값에 가장 작은 값을 /2 한 것을 더한다. 더한 값에 다음으로 작은 값에 /2한 것을 더한다.
순서대로 작은 값을 더해주기 위해 정렬을 했다.
42172KB, 108ms
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = sorted(list(map(int, input().split())))
#제일 양이 많은 에너지 드링크
count = arr[N-1]
#제일 양이 많은 에너지 드링크에 가장 작은 양의 1/2를 더해간다.
for i in range(N-1):
count += arr[i]/2
print(count)
다른 코드 참고해서 수정한 코드
정렬을 하지 않아도 식을 이용하면 max함수와 sum함수를 이용하면 하나의 식으로 해결할 수 있다.
즉, 가장 큰 값 + (모든 양의 합 - 가장 큰 값)/2
정렬을 하지 않으니 속도가 더 빨라 졌다.
42172KB, 72ms
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = list(map(int, input().split()))
print(max(arr) + (sum(arr)-max(arr))/2) # 식 하나로 해결max(arr) + (sum(arr)- max(arr))/2 식도 풀어서 써보면 (sum(arr)+ max(arr))/2 로 바꿀 수 있다. 식을 풀어서 더 계산에 빠른 식이 나오면 그걸 사용하도록 하기.
이 문제의 포인트
- 연산을 줄일 수 있는 식을 찾아 낼 수 있도록 하자
2023. 10. 3 9일차 (2)
11. 20300번 서강근육맨 (실버3) 문제링크
문제 해석
PT를 한번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.
N개의 운동기구를 한번씩 사용할 것이다.
PT를 받을 때는 이전에 사용하지 않았던 운동기구를 선택할 것이다.
한번 PT에 운동기구 2개를 사용하고, 사용하지 않은 운동기구가 하나 남았을 경우에는 PT 1회에 운동기구 하나만 사용한다.
한번 PT를 받을 때 근 손실 정도가 M을 넘지 않도록 한다.
이때 M의 최소값을 구해보자. 두 개를 이용할 때는 두 운동기구의 근손실 정도의 합이다.
제한: 1초 1024MB
입력
첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1<= N <=10,000)
둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t1, t2, ... , tn ( 1 <= ti <= 10^18)
(C로 푼다면 longlong자료형(범위: +-9,223,372,036,854,775,808(약 10^18))을 사용해야하는 것으로 보임)
출력
M의 최솟값을 출력한다.
내 코드
근 손실이 적게 오기 위해서 근손실 값이 가장 큰 운동기구를 사용할 때, 가장 작은 운동기구를 함께 사용해야한다.
N이 홀수 일 때는 근손실 0 짜리 운동기구가 있다고 생각하고 짝수를 맞춰준다.
가장 큰수와 가장 작은 수를 더한 값, 그다음 큰수와 그다음 작은 수를 더한값 .... 중 가장 큰 값이 근손실의 최소값이다.
32464KB 48ms
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = list(map(int, input().split()))
if N%2==1:
arr.append(0)
N+=1
arr.sort()
maxValue = 0
for i in range(N//2):
if arr[i] + arr[N-i-1] > maxValue:
maxValue = arr[i]+arr[N-i-1]
print(maxValue)2023. 10. 4 10일차
12. 19941번 햄버거 분배(실버3) 문제링크
문제 해석
벤치 모양 식탁에 사람들과 햄버거가 일렬로 놓여있다. (햄버거, 사람, 햄버거, 사람, 사람 ....)
사람들은 자신의 위치에서 거리가 K이하인 햄버거를 먹을 수 있다.
식탁의 길이 N, 햄버거를 선택할 수 있는 거리 K가 주어졌을 때,
햄버거를 먹을 수 있는 사람의 최대수를 구하여라.
제한: 0.5초 256MB
입력
첫 줄에 두 정수 N과 K가 있다. 그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.
출력
첫 줄에 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.
내 코드
왼쪽에 있는 사람부터 햄버거를 선택해서 먹게하고, 우측 사람이 최대한 햄버거에 닿게 할 수 있도록 햄버거를 선택한다.
최대 왼쪽 거리에 있는 햄버거를 탐색해서 먹는다.
거리를 줄이면서 왼쪽 것이 없으면 제일 가까운 오른쪽것 부터 최대 오른쪽까지 햄버거를 탐색해서 먹는다.
31424 KB 96ms
import sys
def input():
return sys.stdin.readline().rstrip()
N, K = map(int,input().split())
table = input()
burger = []
person = []
for i in table:
burgerCheck = i=='H'
burger.append(burgerCheck)
person.append(not burgerCheck)
count = 0
for i in range(N):
check = False
if person[i]:
#왼쪽 끝부터 확인
for j in range(K, 0, -1):
if i-j >= 0 and burger[i-j]:
burger[i-j] = False
count+=1
check = True
break
#오른쪽 가까운 곳 부터 확인
if not check:
for j in range(1, K+1):
if i+j < N and burger[i+j]:
burger[i+j] = False
count+=1
break
print(count)2023. 10. 5 11일차
13. 11399번 잃어버린 괄호 (실버2) 문제링크
문제 해석
양수와 +, -, 괄호를 가지고 식을 만들었다.
그리고 괄호를 모두 지웠다.
그리고 괄호를 적절히 쳐서 이 식의 값을 최대로 만들려고 한다.
이 식의 값을 최소로 만드는 프로그램을 작성하여라.
제한: 2초 128MB
입력
첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다. 입력으로 주어지는 식의 길이는 50보다 작거나 같다.
출력
첫째 줄에 정답을 출력한다.
내 코드
마이너스 뒤 연산은 +도 빼기 연산으로 해준다.
-뒤에 나오는 +는 다 괄호로 묶어서 마이너스 하는 값을 키운다. ex) 55-33+44 → 55 - (33+44)
마이너스가 나오기전 +연산만 더하기 연산을 해준다.
34820KB 116ms
import re
S = input()
arr = list(map(int, re.split(r'-|\+', S)))
arrLen = len(arr)
idx = 1
res = arr[0]
minusCheck = False
for i in S:
# '-'가 한번 이상 나왔다면 +도 - 연산을 해준다.
if i=='-' or (i=='+' and minusCheck):
minusCheck = True
res -= arr[idx]
idx+=1
elif i=='+':
res += arr[idx]
idx+=1
if idx == arrLen:
break
print(res)
다른 사람 코드
나는 re 라이브러리를 사용해서 -, + 를 기준으로 잘라주고 각각을 계산했는데
이 분 코드에서는 - 기준으로 먼저 자르고 그 덩어리를 + 연산을 해주고 마지막에 마이너스 연산을 하는 방법을 사용하셨다.
그래서 split()연산만 사용해도 된 코드
30616KB 32ms
#마이너스 기준으로 식을 분리하고
exp = input().split('-')
num = []
#분리된 식을 다 더하기 연산을 해주고
for i in exp:
cnt = 0
sum = i.split('+')
for j in sum:
cnt += int(j)
num.append(cnt)
#더하기 연산한 덩어리의 값을 첫 값에 빼준다.
ans = num[0]
for i in range(1, len(num)):
ans -= num[i]
print(ans)이 문제의 포인트
- 여러 문자열을 기준으로 split할 때 re 라이브러리를 사용하면 된다. split 첫번째 인자에 | 로 구분해서 나눌 문자열을 입력한다.
import re
print(input().split('a|b', '안녕a안녕b안녕'))- 식에 괄호를 쳐서 최소값으로 만들 때는 마이너스 뒤 값은 다 마이너스 연산을 해주면 된다.
2023. 10. 6 12일차
14. 20365번 블로그2 (실버3) 문제링크
문제 해석
매일 아침 풀고싶은 문제를 올린다.
매일 밤 각각의 문제에 대해 해결은 파란색, 미해결은 빨간색으로 칠한다.
문제를 칠할 때의 과정
1. 연속된 임의의 문제들을 선택한다.
2. 선택된 문제들을 전부 원하는 같은색으로 칠한다.
매일 500,000문제까지 시도한다. 가장 효율적인 방법으로 문제를 칠하기를 원한다.
각 문제를 주어진 색으로 칠할 때 필요한 최소한의 작업 횟수를 구하여라.
제한: 2초 1024MB
입력
첫째 줄에 색을 칠해야 하는 문제의 수 N (1 ≤ N ≤ 500,000)이 주어진다.
둘째 줄에 N개의 문자가 공백 없이 순서대로 주어진다. 각 문자는 i번째 문제를 어떤 색으로 칠해야 하는지를 의미하며, R은 빨간색, B는 파란색을 나타낸다. 그 외에 다른 문자는 주어지지 않는다.
출력
첫째 줄에 일우가 주어진 모든 문제를 원하는 색으로 칠할 때까지 필요한 작업 횟수의 최솟값을 출력하라.
내 코드
파랑, 빨강 중에 색의 분할 개수가 많은 것을 처음부터 끝까지 칠하고, 분할 개수가 적은 것을 그 위에 덮어 칠한다.
(B가 분할된 횟수, R이 분할된 횟수 중 작은 값)에 +(1)을 한다.
+1의 의미: 제일먼저 처음부터 끝까지 한색으로 한번 칠하는 것
둘중 작게 분할된 횟수: 한색으로 한번 칠한 후 위에 덮어 칠하는 횟수
32236KB 180ms
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
s = input()
#이전 컬러를 기록해둔다.
preColor = s[0]
#나눠져있는 개수를 저장할 변수
blue = 0
red = 0
if s[0]=='B':
blue = 1
else:
red = 1
for i in range(1,N):
#처음부터 뒤로 탐색하다가 새로운 색깔이 시작되면 그 색의 개수를 올린다.
if s[i]=='B' and preColor=='R':
blue +=1
elif s[i]=='R' and preColor =='B':
red +=1
preColor = s[i]
print(min(blue, red)+1)다른 사람코드
속도가 더 나은 코드가 있는데 잘 이해가 가지는 않는다. ㅠ
32236KB 48ms
n = int(input())
neighbor = input()
print(max(neighbor.count('RB'), neighbor.count('BR')) + 1)2023. 10. 7 13일차
❌ 15. 16953번 A->B (실버2) 문제링크
문제 해석
정수 A를 B로 바꾸려고 한다.
가능한 연산은 두가지다. (1) 2를 곱한다. (2) 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산 횟수의 최솟값을 구해보자.
제한: 2초 512MB
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
아이디어
이 문제는 어떻게 해야 최소 연산을 할 수 있는지 알아차리지 못했다.
따라서 이 문제는 답을 보고 푼 문제이다.
B값을 보면 이전에 어떤 연산으로 B값이 나왔는지 보인다.
B값에서 A로 역연산을 한다.
A:2 B:162 이면
B의 제일 끝자리가 짝수이면 이전 연산에서 2곱하기 연산을 한 것이고
B의 제일 끝자리가 1이면 이전 연산에서 1을 붙이는 연산을 한 것이라고 생각하고
이 과정을 반복해서 A 값이 나올 때까지 연산을 한다.
두 연산이 안되면 A는 B가 될 수 없는 것이다.
A에서 B로 가는 방법은 무수히 많을 수 있지만. B에서 A로 가는 방법은 하나다.
(사실 B에서 A로 가는게 최소라는 것이 바로 인지는 안되지만, B에서 A로 가는 방법이 하나니까 그게 최소값이려니 했다. )
내 코드
31120kb 40ms
def fun(A, B):
count = 0
while A <= B :
if A==B:
return count+1 # +1한 값을 출력하라고 했으므로 +1해준다.
# +1 안하려면 count 의 초기값을 1로 설정해주면 된다.
if B%2==0:
B/=2
count +=1
elif B%10 == 1:
B = (B-1)/10
count +=1
else:
break
return -1
a, b = map(int, input().split())
print(fun(a,b))2023. 10. 8 14일차
16. 21314번 민겸 수 (실버2) 문제링크
문제 해석
민겸이가 만든 새로운 수 체계인 민겸 수
0이상의 정수 N에 대해 10^N 또는 5*10^N 꼴의 십진수를 대문자 M과 K로 이루어진 문자열로 표기한다.
10^N 꼴의 십진수는 N+1개의 M으로
5*10^N 꼴의 십진수는 N개의 M뒤에 1개의 K를 이어붙인 문자열로 나타낸다.
ex) 1(M), 5(K), 10(MM), 50(MK), 100(MMM), 500(MMK), 1000(MMMM), 5000(MMMK)
민겸수는 한 개 이상의 민겸 숫자를 이어붙여 만든다.
ex)MKKMMK는 MK, K, MMK 세 민겸 숫자를 이어붙여 만들 수 있다.
민겸 수를 십진수로 변환할 때 1개 이상의 민겸 숫자로 문자열을 분리한 뒤, 각각의 민겸 숫자를 십진수로 변환해서 순서대로 이어붙이면된다.
민겸 수가 십진수로 변환되었을 때 가질 수 있는 최댓값과 최솟값을 구하자.
제한: 1초 1024MB
입력
민겸 수 하나가 주어진다. 민겸 수는 대문자 M과 K로만 이루어진 문자열이며, 길이는 3,000을 넘지 않는다.
출력
주어진 민겸 수가 십진수로 변환되었을 때 가질 수 있는 값 중 가장 큰 값과 가장 작은 값을 두 줄로 나누어 출력한다.
내 코드
최대 값
앞에서부터 문자를 탐색하면서 K가 나오면 5 * 10 ^(이전에 나온 M의 개수) 로 변환한다.
K가 하나도 없으면 M은 다 1로 변환한다.
최솟 값
연속된 M은 10^(연속된 M의 개수-1)로 변환한다.
K는 5로 변환한다.
31120KB 40ms
strArr = input()
m = 0
maxValue = ''
minValue = ''
for i in strArr:
if i=='M':
m +=1
else: #K
if m==0: #0 예외 처리 해줘야한다.
minValue += '5'
else:
minValue += (str(pow(10, m-1))+'5')
maxValue += str(5*pow(10, m))
m = 0
if m > 0:
minValue += str(pow(10, m-1))
maxValue += ('1'*m)
print(maxValue)
print(minValue)2023. 10. 9 15일차
17. 11501번 주식 (실버2) 문제링크
문제 해석
주식을 하기위한 3가지 행동을 한다.
1. 주식을 하나를 산다.
2. 원하는 만큼 가지고 있는 주식을 판다.
3. 아무것도 안한다.
날 별로 주식의 가격을 알려줬을 때, 최대 이익이 얼마나 되는지 계산해달라.
ex) 날 수가 3일
case1 날별 주가 10, 7, 6 : 주가가 계속 감소하므로 최대 이익은 0이 된다.
case2 날별 주가 3, 5, 9 : 처음 두날에 주식을 하나씩 사고, 마지막 날 다 팔아버리면 이익이 10이 된다.
제한: 5초 256MB
입력
입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타내는 N개의 자연수들이 공백으로 구분되어 순서대로 주어진다. 날 별 주가는 10,000이하다.
출력
각 테스트케이스 별로 최대 이익을 나타내는 정수 하나를 출력한다. 답은 부호있는 64bit 정수형으로 표현 가능하다.
내 코드
해당 날짜의 이익 = 뒷 순서의 가장 큰 수 - 현재 수
값을 뒤에서 부터 순회한다.
뒤에서 부터 가장 큰 값을 업데이트하면서
그 다음에 오는 값과 가장 큰 값과의 차이를 이익으로 더한다.
Python3 : 171.936MB 3.232초
PyPy3: 341.928MB 1.448 초
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
for _ in range(N):
M = int(input())
values = list(map(int,input().split()))
maxValue = 0
res = 0
for i in range(M-1, -1, -1):
value = values[i]
if maxValue < value:
maxValue = value
continue
else:
res += (maxValue - value)
print(res)
이 문제의 포인트
* 1,000ms = 1초
* 1,000kb = 1MB
* 입력할 수 있는 날짜 수가 백만이라는 것에 유의해야한다. 연산의 횟수가 5초를 넘지 않도록 생각해야한다.
* 그리디 알고리즘을 써서 한번만 순회하도록 해서 시간 조건을 충족시킬 수 있도록 했다.
* Pypy3으로 돌리면 메모리는 더 많이 쓰면서 더 빠르다.
2023. 10. 10 16일차
18. 1080번 행렬 (실버1) 문제링크
문제 해석
0과 1로만 이루어진 행렬 A와 B가 있다.
행렬 A를 행렬 B로 바꾸는데 필요한 연산의 횟수의 최솟값을 구하는 프로그램을 작성하여라.
행렬 변환 연산은 3x3 크기의 부분행렬에 있는 모든 원소를 뒤집는 것이다.(0->1, 1->0)
A를 B로 바꿀 수 없다면 -1을 출력.
제한: 2초 128MB
입력
첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.
출력
첫째 줄에 문제의 정답을 출력한다. 만약 A를 B로 바꿀 수 없다면 -1을 출력한다.
내 코드
순서대로 순회해서 B행렬이랑 다르면 3x3 을 다 뒤집는다.
그러면 최대 칸 횟수만큼 연산을 하는 것이고 뒤집어서 안나오면 안되는 것이라고 판단한다.
31MB 44ms
import sys
def input():
return sys.stdin.readline().rstrip()
def swap(i, j):
if i+2 >= N or j+2 >= M:
return 0
cx = [i,i+1,i+2]
cy = [j,j+1,j+2]
for i in cx:
for j in cy:
if arrA[i][j] ==0:
arrA[i][j] = 1
else:
arrA[i][j] = 0
return 1
N, M = map(int, input().split())
arrA = []
arrB = []
for _ in range(N):
arrA.append(list(map(int, input())))
for _ in range(N):
arrB.append(list(map(int, input())))
count = 0
for i in range(N):
for j in range(M):
if arrA[i][j] != arrB[i][j]:
count += swap(i,j)
check = True
for i in range(N):
for j in range(M):
if arrA[i][j] != arrB[i][j]:
check = False
break
if check:
print(count)
else:
print(-1)
다른 사람 코드에서 배울 점
문자열을 입력받아서 리스트로 만들때 리스트 안에 바로 for 문을 사용한다.
두 리스트의 값이 같은지 비교할 때는 == 연산을 사용하면 된다.
3x3 범위를 지정하기 위해서 range(n-2) , range(n-2) 까지만 참조할 수 있도록 한다.
해당인덱스의 +1, +2 한 인덱스를 참조하기 위해서는 range(i, i+3) 을 사용해보자.
0과 1을 토글하기 위해서는 1에 해당 값을 빼자.
30MB 40ms
def reverse(a, b):
for i in range(a, a+3):
for j in range(b, b+3):
A[i][j] = 1 - A[i][j] # 토글
n, m = map(int, input().split())
A = [list(map(int, input())) for _ in range(n)]
B = [list(map(int, input())) for _ in range(n)]
cnt = 0
for i in range(n-2):
for j in range(m-2):
if A[i][j] != B[i][j]:
reverse(i, j)
cnt += 1
if A == B:
print(cnt)
else:
print(-1)
이 문제의 포인트
* 처음부터 끝까지 한번만 순회하면서 값을 한번에 구할 수 있도록 한다. (그리디 알고리즘)
* 리스트의 값이 같은지 비교할 때는 == 연산자를 사용한다.
* 문자열 숫자행렬을 입력 받을 때는 [list(map(int,input()) for _ in range(N)]을 사용해보자.
* 0과 1을 토글 하기 위해서는 1에 해당 값을 뺀다.
2023. 10. 11 17일차
19. 1931번 회의실 배정 (실버1) 문제링크
문제 해석
한 개의 회의실에서 N개의 회의에대한 회의실 시간표를 만들려고 한다.
회의 시작시간과 끝나는 시간이 주어져 있고,
각 회의가 겹치지 않게하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자
회의의 시작시간과 끝나는 시간이 같을 수 있다.
제한: 2초 128MB
입력
첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 2^31-1보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.
내 코드
끝나는 시간에 대해 오름차순으로 정렬하고
이전에 끝난 시간을 0을 초기값으로 두고
0시부터 시작해서 1씩 올려가면서
끝나는 시간이 이전 끝값보다 같거나 크다면 끝나는 시간 값을 업데이트한다. 회의 횟수도 카운트
59MB 0.28초
(readline()안썼을 때는 4.2초 였음. 십만개에서도 15배가 차이나는 걸 볼 수 있음. 꼭 readline 쓰기!)
import sys
def input():
return sys.stdin.readline().rstrip()
N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
end = 0
count =0
arr.sort(key=lambda x:(x[1],x[0]))
for i in range(N):
if arr[i][0] >= end:
end = arr[i][1]
count += 1
print(count)
이 문제의 포인트
* 이차원 배열의 특정 인덱스를 기준으로 하는 정렬
- 두번째 요소를 기준으로 정렬 sorted(key=lambda x:x[1])
- 두번째 요소를 기준으로 정렬된 값을 값이 같을 경우 첫번째 요소를 기준으로 내림차순 정렬 sorted(key lambda x:(x[1], -x[0]))
- 내림차순이면 '-' 를 붙인다.
- 정렬하고 싶은 순서대로 쓴다.
- 추가 예시) 첫번째 요소를 기준으로 정ㄹ하고 값이 같을 경우 두번째 요소를 오름차순 정렬 sorted(key = lambda x:(x[0],x[1]))
* 백만개 입력받을 때 그냥 input쓰는거랑 readline쓰는게 15배가 차이났음. 입력이 많을 때는 readline을 쓰도록 하자.
2023. 12. 05. 1일차(1) 다시시작!
❌ 20. 17615번 볼 모으기 (실버1) 문제링크
문제 해석
빨강 파랑 볼이 일직선 상에 놓여있을 때, 볼을 옮겨서 같은 공끼리 인접하게 놓이도록 하려고 한다.
볼을 옮기는 규칙
1. 바로 옆에 다른 색깔의 볼이 있으면 그 볼을 모두 뛰어 넘을 수 있다.
2. 옮길 수 있는 볼의 색은 한가지이다. 즉, 빨간 볼을 처음에 옮겼으면 다음에는 빨간공만 옮길 수 있다.
일직선 상에 놓여있는 볼에 관한 정보가 주어질 때, 규칙에 따라 볼을 이동하여 같은 색끼리 모으되 최소 이동 횟수를 찾는 프로그램을 작성하시오.
제한: 1초 512MB
입력
첫 번째 줄에는 볼의 총 개수 N이 주어진다. (1 ≤ N ≤ 500,000) 다음 줄에는 볼의 색깔을 나타내는 문자 R(빨간색 볼) 또는 B(파란색 볼)가 공백 없이 주어진다. 문자열에는 R 또는 B 중 한 종류만 주어질 수도 있으며, 이 경우 답은 0이 된다.
출력
최소 이동횟수를 출력한다.
해석참고: https://newdeal123.tistory.com/9#%EC%B6%9C%EB%A0%A5-1
아이디어
- 답은 무조건 4가지의 경우 중의 하나로 나타난다.
예제와 같은 RBBBRBRRR의 공의 배열이 주어질 때,
R만 움직여 RRRRRBBBB, R만 움직여 BBBBRRRRR
B만 움직여 RRRRRBBBB, B만 움직여 BBBBRRRRR
- R만 움직여 RRRRRBBBB를 어떻게 만들수 있을까?
제일 왼쪽에 있는 R부터 가장 왼쪽으로 이동 시킨다. R이 B뭉텅이를 최소한의 횟수로 뛰어 넘게 하기 위해서 B를 최대한 모을 수 있도록 하기 위함이다.
결론적으로
- R을 오른쪽으로 이동시키고 싶으면 제일 오른쪽 R부터 오른쪽으로 이동
- R을 왼쪽으로 이동시키고 싶으면 제일 왼쪽 R부터 왼쪽으로 이동
- B를 오른쪽으로 이동시키고 싶으면 제일 오른쪽 B부터 오른쪽으로 이동
- B를 왼쪽으로 이동시키고 싶으면 제일 왼쪽 B부터 왼쪽으로 이동
코드
- (R/B)색을 (오른/왼)쪽으로 이동시키고 싶다면 제일 (오른/왼)쪽에 있는 (R/B)볼은 이동을 안해도 되므로 제거하고, 제거하고 남아있는 볼의 개수가 이동 횟수이다.
3.2MB 0.052초
import sys
def input():
return sys.stdin.readline().rstrip()
N = input()
Ball = input()
#R을 오른쪽으로 이동시켜 R을 오른쪽으로 모은다.
minCount = str(Ball).rstrip('R').count('R')
#B를 오른쪽으로 이동시켜 B를 오른쪽으로 모은다.
count = str(Ball).rstrip('B').count('B')
if minCount > count:
minCount = count
#R을 왼쪽으로 이동시켜 R을 왼쪽으로 모은다.
count = str(Ball).lstrip('R').count('R')
if minCount > count:
minCount = count
#B를 왼쪽으로 이동시켜 R를 왼쪽으로 모은다.
count = str(Ball).lstrip('B').count('B')
if minCount > count:
minCount = count
print(minCount)이 문제의 포인트
* 나올 수 있는 모든 경우를 생각해본다.
* 양 끝에있는 특정 문자를 (묶음으로) 삭제하는 함수: rstrip('문자'), lstrip('문자'), strip('문자')
- 인자를 넣지 않으면 양끝에 있는 엔터, 공백, 탭을 삭제한다.
- 여러개를 지정할 수 있다. strip('문자', '문자')
* 문자열 복사 방법 : str(myStr) or myStr[:] or ""+myStr
2023. 12. 05. 1일차 (2)
❌ 21. 2138번 전구와 스위치 (골드5) 문제링크
문제 해석
N개의 스위치 N개의 전구가 있다.
i(1<i<N)번 스위치를 누르면 i-1, i, i+1의 세개의 전구의 상태가 바뀐다.
꺼져있는 전구는 켜지고, 켜져 있는 전구는 꺼지게 된다.
1번 스위치를 눌렀을 경우에는 1,2번의 전구의 상태가 바뀌고, N번 스위치를 눌렀을 경우에는 N-1, N 번 전구의 상태가 바뀌게 된다.
N개의 전들의 현재상태와 우리가 만들고자 하는 상태가 주어졌을 때 그 상태를 만들기 위해 스위치를 누르는 최소 횟수를 구하여라.
제한: 2초 128MB
입력
첫째 줄에 자연수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 전구들의 현재 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 그 다음 줄에는 우리가 만들고자 하는 전구들의 상태를 나타내는 숫자 N개가 공백 없이 주어진다. 0은 켜져 있는 상태, 1은 꺼져 있는 상태를 의미한다.
출력
첫째 줄에 답을 출력한다. 불가능한 경우에는 -1을 출력한다.
아이디어
- 순차적으로 탐색한다면 i 번째 스위치가 i-1번째 전구의 상태를 결정할 마지막 스위치이다.
- 0번째 스위치를 누르면서 시작할지, 누르지 않으면서 시작할지의 경우를 두 가지로 나눌 수 있다.
- 0번째 스위치를 누를지말지가 결정되면 나머지는 i-1 에 따라서 결정된다.
- 이렇게 경우의 수를 고정해서 풀어보는 것을 생각해봐야한다.
코드1
1,0 int 형으로 변환해서 사용한 코드
33MB, 96ms
import sys
def input():
return sys.stdin.readline().rstrip()
def fun(arr, target):
count = 0
for i in range(1, N):
# i-1 이 target 과 다르다면 i스위치를 누른다.
if arr[i - 1] != target[i - 1]:
count += 1
arr[i - 1] = 1 - arr[i-1]
arr[i] = 1 - arr[i]
if i < N - 1:
arr[i + 1] = 1 - arr[i+1]
if arr == target:
return count
else:
return -1
N = int(input())
bulb = list(map(int, input()))
target = list(map(int, input()))
if bulb == target:
print(0)
else:
#첫번째 스위치를 누르지 않는다.
res1 = fun(bulb[:],target)
#첫번째 스위치를 누른다.
bulb[0] = 1 - bulb[0]
bulb[1] = 1 - bulb[1]
res2 = fun(bulb[:],target) + 1
if res1 > 0 and res2 > 0:
print(min(res1, res2))
elif res1 >0:
print(res1)
elif res2 >0:
print(res2)
else:
print(-1)
코드 2
1,0 문자로 그대로 사용한 코드
33MB, 80ms
import sys
def input():
return sys.stdin.readline().strip()
def fun(arr, target, count):
if count ==1:
# 첫번째 스위치를 누르는 경우
arr[0] = '1' if arr[0] == '0' else '0'
arr[1] = '1' if arr[1] == '0' else '0'
for i in range(1, N):
# i-1 이 target 과 다르다면 i스위치를 누른다.
if arr[i - 1] != target[i - 1]:
count += 1
arr[i - 1] = '1' if arr[i - 1] == '0' else '0'
arr[i] = '1' if arr[i] == '0' else '0'
if i != N - 1:
arr[i + 1] = '1' if arr[i + 1] == '0' else '0'
if arr == target:
return count
else:
return -1
N = int(input())
bulb = list(input())
target = list(input())
if bulb == target:
print(0)
else:
count = 1
res1 = fun(bulb[:],target, 1)
res2 = fun(bulb[:],target, 0)
if res1 > 0 and res2 > 0:
print(min(res1, res2))
elif res1 > 0:
print(res1)
elif res2 > 0:
print(res2)
else:
print(-1)
이 문제의 포인트
* 이 문제도 결국 풀어볼 수 있는 모든 경우를 생각해보는데서 시작해야하는 것 같다. 스위치 0번을 누르냐 안누르냐에 따라 경우의 수가 두개가 나온다는 것을 파악해야한다. (위 20번째 풀어본 볼 모으기 문제에서도 전체 나올 수 있는 경우를 먼저 생각해봤다. 그리디 문제를 풀때는 경우의 수를 생각해보자.)
* min(res1, res2) 코드에서 print로 결과를 출력해줘야하는데 min(res1,res2)라고 만 써둬서 1시간을 헤매었다....!! print가 없어도 출력됐던 코랩 쓸때의 부작용이다. 으아아악!! 내 한시간....ㅠㅠㅠ
* 1,0 을 토글 할 때는 int로 타입변환 해서 사용하자. 1과 0 전환은 1에다가 해당 숫자를 빼주면되기 때문.
2023. 12. 05. 1일차(3)
❌ 22. 21758번 꿀따기 (골드5) 문제링크
문제 해석
일렬로 N개의 장소가 주어진다.
2개의 장소에는 벌이, 한 장소에는 벌통이 있다. (모두 다른 장소)
벌은 벌통으로 날아가면서 모든 칸에서 꿀을 딴다. (벌통이 있는 칸도 꿀을 딴다.)
두 마리모두 표시된 양만큼의 꿀을 딴다.
벌이 시작한 장소에서는 어떤 벌도 꿀을 딸 수 없다. (시작하는 벌도)
장소별꿀 양을 입력 받아 벌들이 딸 수 있는 최대의 꿀 양을 계산하는 프로그램을 작성하라.
제한: 1초 512MB
입력
첫 번째 줄에 장소의 수 N이 주어진다.
다음 줄에 왼쪽부터 각 장소에서 꿀을 딸 수 있는 양이 공백 하나씩을 사이에 두고 주어진다.
출력
첫 번째 줄에 가능한 최대의 꿀의 양을 출력한다.
제한
3 <= N <= 100,000
각 장소의 꿀의 양은 1이상 10,000이하의 정수이다.
해석 참고: https://sodehdt-ldkt.tistory.com/53
아이디어
꿀통의 위치에 따라 세가지 경우로 나누어볼 수 있다.
(1) 꿀통이 제일 왼쪽에 있는 경우 - 하나의 벌이 제일 오른쪽에 위치하고, 나머지 벌은 사이에 위치한다.
(2) 꿀통이 제일 오른쪽에 있는 경우 - 하나의 벌이 제일 왼쪽에 위치하고, 나머지 벌은 사이에 위치한다.
위 두가지 경우는 벌을 옮겨가며 꿀의 합을 구한다.
(3) 꿀통이 벌 사이에 있는 경우 - 하나의 벌은 제일 오른쪽, 나머지 벌은 제일 왼쪽에 위치하고, 벌통을 벌 사이에 위치한다.
3번째 경우는 꿀통을 옮겨가며 꿀의 합을 구한다. 꿀통부분을 두개의 벌이 다 먹을 수 있다는 것을 주의해야한다.
코드 1
100점 코드. 해석참고 해서 누적합으로 구한 코드이다.
388ms
import sys
def _input():
return sys.stdin.readline().strip()
N = int(_input())
arr = list(map(int, _input().split()))
sumList = [arr[0]]
# 누적합을 구한다.
for i in range(1, N):
sumList.append(sumList[i-1] + arr[i])
result = 0
# 벌이 있는 자리는 먹지 않는다.
# 꿀통이 제일 왼쪽에 있는 경우 벌한마리는 제일 오른쪽에 위치하고, 나머지 한 마리는 최대꿀을 먹을 수 있도록 배치한다.
for i in range(1, N-1):
result = max(result,sumList[N - 2] - arr[i] + sumList[i - 1])
# 제일 오른쪽에 있는 벌이 먹는 꿀양 + 사이에 있는 벌이 먹는 꿀 양
# 꿀통이 제일 오른쪽에 있는 경우. 벌한마리는 제일 왼쪽에 위치하고, 나머지 한 마리는 최대꿀을 먹을 수 있도록 배치한다.
for i in range(1, N-1):
result = max(result,sumList[N - 1] - arr[0] - arr[i] + sumList[N - 1] - sumList[i])
# 제일 왼쪽에 있는 벌이 먹는 꿀양 + 사이에 있는 벌이 먹는 꿀 양
# 꿀통이 벌 사이에 있는 경우. 벌통은 양 끝만 아니면됨.
# 양끝은 먹지않고 벌통있는 부분을 두마리의 벌이 다 먹는다.
for i in range(1, N-1):
result = max(result,sumList[N - 2] - arr[0] + arr[i])
print(result)
코드 2
누적합을 구하지 않고 처음에 모든 꿀의 합을 구해두고 값을 구했다.
55점이 나왔는데 왜그런지 파악을 못했다.
for 안에 sum을 사용하지 말고 해볼까? 나중에 다시 풀어 봐야겠다.
import sys
def _input():
return sys.stdin.readline().strip()
N = int(_input())
arr = list(map(int, _input().split()))
honey = sum(arr)
result = 0
# 벌이 있는 자리는 먹지 않는다.
# 꿀통이 제일 왼쪽에 있는 경우 벌한마리는 제일 오른쪽에 위치하고, 나머지 한 마리는 최대꿀을 먹을 수 있도록 배치한다.
# 나머지 벌한 마리의 위치를 옮기며 최대 값을 찾는다.
for i in range(1, N-1):
# 사이에 있는 벌이 먹는 꿀 양
bee1 = sum(arr[:i])
# 제일 오른쪽에 있는 벌이 먹는 꿀양
bee2 = honey - arr[-1] - arr[i]
if result < bee1 + bee2:
result = bee1 + bee2
# 꿀통이 제일 오른쪽에 있는 경우. 벌한마리는 제일 왼쪽에 위치하고, 나머지 한 마리는 최대꿀을 먹을 수 있도록 배치한다.
# 나머지 벌한 마리의 위치를 옮기며 최대 값을 찾는다.
for i in range(1, N-1):
# 사이에 있는 벌이 먹는 꿀 양
bee1 = sum(arr[i+1:])
# 제일 왼쪽에 있는 벌이 먹는 꿀양
bee2 = honey - arr[0] - arr[i]
if result < bee1 + bee2:
result = bee1 + bee2
# 꿀통이 벌 사이에 있는 경우. 벌통은 양 끝만 아니면됨. 1에 뒀다고 생각하고 구하자
# 양끝은 못먹고 꿀통이 놓인곳은 두마리다 먹기때문에 꿀통이 놓인곳의 꿀양을 더해준다.
for i in range(1, N-1):
bee = honey - arr[0] - arr[-1] + arr[i]
if result < bee:
result = bee
print(result)
이 문제의 포인트
- 경우의 수를 잘 구하는 것이 포인트이다. 대부분의 그리드 알고리즘이 그런 원리인 듯 보인다. 어렵다...
- 꿀통이 있는 곳에 두마리 벌이 둘다 먹을 수 있다는 것을 간과 했었다. 주의 깊게 문제를 풀 필요가 있는 것 같다.
- 문제 풀때 빨리 풀려고 하다보니 문제 파악을 잘 못하고 푸는 것 같다. 집중하자.
추가문제
23. 11000번 강의실 배정 (골드 5) 문제링크
24. 13164번 행복 유치원 (골드 5) 문제링크
25. 19598번 최소 회의실 개수 (골드 5) 문제링크
26. 2212번 센서 (골드 5) 문제링크
27. 1092번 배 (골드 5) 문제링크
28. 1863번 스카이라인 쉬운거 (골드 5) 문제링크
29. 2141번 우체국 (골드 4) 문제링크
30. 13975번 파일 합치기 3 (골드 4) 문제링크
31. 1715번 카드 정렬하기 (골드 4) 문제링크
32. 2812번 크게 만들기 (골드 3) 문제링크
33. 24337번 기회와 탑 (골드 3) 문제링크
34. 8980번 택배 (골드 2) 문제링크
35. 3687번 성냥개비 (골드 2) 문제링크
36. 1202번 보석 도둑 (골드 2) 문제링크
37. 1700번 멀티탭 스케줄링 (골드 1) 문제링크
38. 18185번 라면 사기 (Small) (플레 4) 문제링크
'알고리즘 문제풀이' 카테고리의 다른 글
| 동적계획법(DP) 문제 및 풀이 (Python) (0) | 2023.12.04 |
|---|---|
| 완전탐색(브루트포스) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 너비 우선 탐색(BFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 깊이 우선 탐색(DFS) 문제 및 풀이 (Python) (0) | 2023.12.04 |
| 코테 준비를 위한 알고리즘 공부 순서 (0) | 2023.09.25 |