Problem Solving/BOJ - Python (23) 썸네일형 리스트형 [Python | 파이썬] 백준 2565 전깃줄 [Python | 파이썬] 백준 2565 전깃줄 dp 배열에는 지우지 않을 수 있는 최대 전깃줄 개수를 저장한다. A 전봇대에 위치하는 전봇대들의 인덱스를 i라고 하면, i번째 인덱스까지 존재할 수 있는 최대 전깃줄의 개수는 0번부터 i-1번까지의 전깃줄 중에서 그 전깃줄의 B 전봇대에서의 인덱스가 i번째 인덱스의 값보다 작거나 같은 전깃줄 수의 합 + 1 (i번째 전깃줄) 이다. for i in range(1, n): for j in range(i): if arr[j][1] < arr[i][1]: dp[i] = max(dp[i], dp[j] + 1) 그리고 문제에서 삭제해야하는 전깃줄의 최소 갯수를 물어봤으므로 n - max(dp) 를 출력하면 된다. 더보기 n = int(input()) arr = [.. [Python | 파이썬] 백준 2156 포도주 시식 [Python | 파이썬] 백준 2156 포도주 시식 포도주는 연속으로 3잔을 마실 수 없다. 만약 4번째 포도주를 마신다고 하면 2가지 경우가 가능하다. 1 2 3 4 o o x o => dp[1] + grape[2] + grape[4] => dp[i-3] + grape[i-2] + grape[i] o x o o => dp[1] + grape[3] + grape[4] => dp[i-3] + grape[i-1] + grape[i] 4번째 포도주를 안마신다고 하면 3번째 포도주를 마셨을 때까지의 경우가 최대의 경우이다. 1 2 3 4 o o x x o x o x x o o x ~~ 앞에가 어떻든 간에 3번째 까지의 최대의 값이 4번째로 이어져 온다. dp[4] = dp[3] => dp[i-1] 따라서 3가.. [Python | 파이썬] 백준 1147 RGB 거리 [Python | 파이썬] 백준 1147 RGB 거리 dynamic programming을 이용해 푸는 문제이다. 1번부터 N번 집까지 각각 빨간색, 초록색, 파란색을 색칠하였을 경우 그 다음 번호의 집이 색칠할 수 있는 경우의 수는 2가지가 존재한다. arr[0][0]을 첫번째 집을 빨간색, arr[0][1]을 초록색, arr[0][2]를 파란색을 색칠했을때의 비용이라고 생각한다. 그리고 arr[n-1][0]은 n번째 집을 빨간색, arr[0][1]을 초록색, arr[0][2]를 파란색을 색칠했을때의 비용이라고 생각한다. 1부터 n-1까지 차례대로 반복문을 통해 arr[house][i]에 대해서 i == 0(현재 집을 빨간색으로 칠할때) i == 1(초록) i == 2 (파랑) 각각의 경우의 수에대해서.. [Python | 파이썬] 백준 13305 주유소 [Python | 파이썬] 백준 13305 주유소 처음 풀었던 코드는 실행시간을 초과하였다. 그래서 다른 사람의 풀이를 참고해서 풀었다. min_cost는 앞에서부터 가장작은 기름의 값을 보관해두는 변수이다. 현재 인덱스의 oils[r]이 min_cost보다 작다면 갱신해준다. 참고한 블로그: https://alpyrithm.tistory.com/134 더보기 나중 풀이 import sys input = sys.stdin.readline n = int(input()) roads = list(map(int, input().split())) oils = list(map(int, input().split())) cost = 0 min_cost = oils[0] for r in range(n-1): if oil.. [Python | 파이썬] 백준 1541 잃어버린 괄호 [Python | 파이썬] 백준 1541 잃어버린 괄호 - 기호를 기준으로 구분한 묶음에 대해서 + 기호를 기준으로 구분하여 묶음을 계산하고 각 묶음의 첫번째 값을 시작으로 하여 두번째묶음부터 계속 빼주는 연산을 하면 된다. (첫번째 묶음) - (두번째 묶음) - (세번째 묶음) 참고한 블로그: https://pacific-ocean.tistory.com/228 더보기 # import re s = input().split('-') ans = 0 # a = re.split('[+-]', s) arr = [] for i in s: cnt = 0 tmp = i.split('+') for j in tmp: cnt += int(j) arr.append(cnt) ans = arr[0] for i in range(1.. [Python | 파이썬] 백준 11399 ATM [Python | 파이썬] 백준 11399 ATM 기다리는 시간은 앞에서부터 누적되기때문에 인출하는데 걸리는 시간이 가장 짧은 사람부터 정렬하고 차례대로 누적한 값을 계속해서 현재 인출하는데 걸리는 시간과 합하여 count해주면 된다. 더보기 n = int(input()) p = list(map(int, input().split())) cnt = 0 rst = 0 p.sort() for i in p: cnt += i + rst rst += i print(cnt) https://www.acmicpc.net/problem/11399 [Python | 파이썬] 백준 11047 동전0 [Python | 파이썬] 백준 11047 동전0 이 문제는 그리디 알고리즘으로 해결할 수 있다. 이유는 각 동전의 값이 다른 동전의 값의 배수이기 때문이다. 따라서 동전을 내림차순으로 정렬한 뒤에 현재 금액을 가장 큰 동전의 금액으로 나눈 몫을 result에 추가해주고, 나눈 나머지를 현재 금액으로 갱신해주면 된다. 더보기 n, k = map(int, input().split()) coin = [] for i in range(n): coin.append(int(input())) rst = 0 coin.sort(reverse=True) for c in coin: rst += k // c k %= c print(rst) https://www.acmicpc.net/problem/11047 [Python | 파이썬] 백준 1931 회의실 배정 [Python | 파이썬] 백준 1931 회의실 배정 회의시간이 겹치지않게 최대한 많은 회의를 회의실에서 사용할 수 있는 최대 개수를 구하는 문제이다. 따라서 그리디 알고리즘을 이용해서 풀 수 있다. 이때 핵심은 어떻게 입력으로 주어진 각 회의정보를 정렬하느냐이다. 회의정보는 시작시간과 끝시간이 주어지고 시작시간과 끝시간이 같을 수 있다. 이렇게 시작시간과 끝시간이 같은 회의가 존재한다는 조건이 문제풀이의 핵심이 되는 부분이다. 만약 시작시간이 빠른 회의부터 정렬하게 된다면 더 먼저 시작하지만 오래 회의를 하는 회의를 추가하게 되어 최대 개수를 구할 수 없다. 따라서 끝시간이 빠른 회의부터 정렬하는 방법을 생각해볼 수 있다. 일반적으로 시작시간이 같다면 끝시간이 빠른회의를 추가하는게 유리하다. 그리고 이.. 이전 1 2 3 다음 목록 더보기
