본문 바로가기
728x90

ALGORITHM142

[BOJ/Python] 2473. 세 용액 📌 문제 https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 📌 문제 접근 방법 움직이지 않는 기준을 하나 설정하고 왼쪽, 오른쪽 인덱스를 바꿔가면서 합을 도출한다. 합이 양수라면 오른쪽 인덱스를 -1, 음수라면 왼쪽 인덱스를 +1 해줘서 0에 가깝게 만들어준다. 위의 과정을 반복하며 합이 0과 가장 가까운 인덱스 3개를 저장한다. 시간 초과 해결 1, 2의 과정으로는 자꾸 시간 초과가 나서 다음의 시도를 해보았다. 기준점(j.. 2021. 10. 7.
[SWEA/Python] 1865. 동철이의 일 분배 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 재귀로 순열을 구현해서 경우의 수를 찾아주고 확률을 곱해준다. success리스트에 들어있는 확률은 전부 1이하 이므로 total이 max_success보다 작다면, 더 이상 커질 수 없다고 판단하여 리턴시켜서 가지치를 해줬다. 📌 코드 import sys sys.stdin = open('input.txt') def permutation(total): global staff, max_success if total 2021. 10. 7.
[SWEA/Python] 5209. 최소 생산 비용 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 순열이 필요할 것 같아서 itrertools에서 permutations를 import했더니 시간초과! 재귀를 사용해서 순열을 직접 구현해줬더니 통과했다. 비용을 더한 값이 이미 최소 값보다 커졌다면 return을 해줘서 가지치기를 해줬다. 📌 코드 import sys sys.stdin = open('input.txt') def permutation(total): global factory, min_cost if total > min_cost: return if l.. 2021. 10. 7.
[SWEA/Python] 5208. 전기버스2 📌 문제 https://swexpertacademy.com/main/main.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 📌 문제 접근 방법 현재 정류장에서 충전한다면 최대 어디까지 갈 수 있는지를 미리 계산해서 max_station 리스트에 저장한다. 인덱스를 맞춰주기 위해 0번은 비워놓았다. 타겟은 원하는 도착 지점이다. max_station을 순회하면서 타겟까지 도착할 수 있는 정류장이 있다면, 그 정류장을 타겟으로 다시 max_station을 순회하며 해당 정류장까지 도착할 수 있는 정류장을 찾는다. 위의 과정을 반복하며 카운팅한다. 📌 코드 import sys sys.stdin = open('.. 2021. 10. 7.
728x90