백준 그리디

[백준 1343] 폴리오미노 - python

https://www.acmicpc.net/problem/1343 1343번: 폴리오미노 첫째 줄에 사전순으로 가장 앞서는 답을 출력한다. 만약 덮을 수 없으면 -1을 출력한다. www.acmicpc.net 문제 풀이 나의 정답 입력받을 때 '.'을 기준으로 나누도록 했다 for문과 X의 길이를 사용해 풀어냈다 하지만 다른 사람 코드를 보니 꽤 복잡하게 풀어낸 코드였다 poliomino = list(input().split('.')) # print(poliomino) a = 'AAAA' b = 'BB' result = '' print(poliomino) for i in range(len(poliomino)): x_len = len(poliomino[i]) if x_len % 2 == 1: # 홀수개가 있..

[백준 13305] 주유소 - python

https://www.acmicpc.net/problem/13305 13305번: 주유소 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 도시의 개수를 나타내는 정수 N(2 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 인접한 두 도시를 연결하는 도로의 길이가 제일 왼쪽 도로부터 N-1 www.acmicpc.net 문제 풀이 틀린 풀이 이 때 생각은 cost의 값들 중에서 최소값만 찾아 최소값이 나오기 전까지는 다음 목적지까지 가기위한 기름만 사고 최소값이 나오면 끝까지 갈 기름을 사면 된다고 생각했다 하지만 해당 테스트 케이스를 진행했을 때 틀린 것을 확인할 수 있었다 5 1 1 1 1 9 11 5 12 1 해당 테스트 케이스에서 내 코드는 9에서 한번 11에서 한번 5에서 두번을 해서 30..

[백준 2217] 로프 - python

2217번: 로프 (acmicpc.net) 2217번: 로프 N(1 ≤ N ≤ 100,000)개의 로프가 있다. 이 로프를 이용하여 이런 저런 물체를 들어올릴 수 있다. 각각의 로프는 그 굵기나 길이가 다르기 때문에 들 수 있는 물체의 중량이 서로 다를 수도 있다. 하 www.acmicpc.net ' 문제풀이 처음 풀이 임의의 몇개의 로프들을 골라 최대 중량을 구하는 문제이므로 처음에 조합을 생각해냄 일단 최대값을 구하기 위해 lst값을 오름차순 해주었음 조합을 이용해 1개묶음, 2개묶음... n개묶음 까지 구한 후에 combi값에서 가장 큰 값들로만 이루어진 combi[0]에서 최소값 x 로프 개수(k)를 해주었음 하지만 메모리 초과가 떠서 실패,, from itertools import combina..

[백준 14916] 거스름돈 - python

14916번: 거스름돈 (acmicpc.net) 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net ' 문제풀이 1과 3인 경우에는 거스름돈을 줄 수 없음 => -1 최소값을 구해야하므로 5원으로 최대한 나눠줘야하는데 13 경우에는 5원으로 2번나누게 되면 3원이 남아 2원 거스름돈 나눠줄 수 없음 5로 최대한 나눴을 때 남는 수는 1, 2, 3, 4중에 하나이다 나는 n원과 5원의 최대 몫을 구한후에 n의 나머지가 2로 나눠지지 않으면 5원을 한개 더해주어 2로 나누어질 수 있게 했음 (1+5 => 6, 3+ 5 => 8) n = int(input()) count = 0 # 거스름돈 최소 개수 if n == 1 or n == 3: ..