-
1421. [Python]나무꾼 이다솜Python_알고리즘/Silver I 2023. 12. 7. 05:25
1. 문제
https://www.acmicpc.net/problem/1421
2. 접근 방법
- 시간 제한: 2초
- 메모리 제한: 128MB
- 브루트포스
- 구현
3. 파이썬 코드
import sys input = sys.stdin.readline N, C, W = map(int, input().split()) # 나무를 담을 리스트 wood_list = [] for _ in range(N): wood_list.append(int(input())) # 나무를 작은값부터 큰수로 오름차순 정렬 wood_list.sort() max_wood = 0 # 1부터 최대 나무길이까지 반복 for i in range(1, wood_list[-1] + 1): # 현재 가격변수 선언 current_value = 0 # 나무 리스트를 반복하며 for j in wood_list: # 자르는 길이가 나무보다 작은경우 if j > i: # 나무 자른 횟수체크 cut_cnt = j // i # 길이가 남았는지 확인할 변수 r = j % i # 나머지가 없으면 자르는 횟수 -1 if r == 0: cut_cnt -= 1 # 이득값 계산해는 식 몫 * W * 현재 나무 길이 - 자른 횟수 * 자르는 비용 profit = ((j // i) * W * i) - (cut_cnt * C) # 이득값이 음수면 패스 if profit < 0: continue # profit 을 현재 값에 더해나감 current_value += profit # 그냥 j와 i가 같으면 자를필요없이 값 더해줌 elif j == i: current_value += i * W # 최대값 비교 if current_value > max_wood: max_wood = current_value print(max_wood)
4. 문제를 풀고난 후 생각
- 나무의 길이를 1부터 최대 길이까지 잘라가며 이득인 값을 찾는 문제이다.
- 문제를 보며 이득값이 음수인 경우 값을 더해주면 안되고 나무를 안자를 수 있기때문에 그 부분을 주의해서 풀면 된다.
- 처음 풀었던 방식은 자르는 횟수를 구한 후 전체 값 계산하는 부분에서 자르는 횟수를 먼저 빼줘서 답이 이상하게 나왔고 고민을하다가 방식을 다르게 바꿔서 자르고 값을 계산한 부분에서 이득이 되는 값을 뺴주는 방식으로 변경했다.
5. 문제를 푸는데 도움이 되는 지식
- 브루트포스
'Python_알고리즘 > Silver I' 카테고리의 다른 글
1926. [Python]그림 (0) 2023.12.09 1342. [Python]행운의 문자열 (1) 2023.12.08 1527. [Python] 금민수의 개수 (0) 2023.08.30 2667. [Python]단지번호붙이기 (0) 2023.06.04 1697. [Python]숨바꼭질 (0) 2023.03.09