728x90 자료구조22 [python] 백준 19644 좀비 떼가 기관총 진지에도 오다니 https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 문제해결 시물레이션 같은 문제이지만 시물레이션으로 생각하고 구현하면 시간초과가 나기 쉽다. (O(n))으로 풀어야 한다. 기관총이 1부터 ml까지 영향을 주기 때문에 기관총에 영향을 받았을 때 체력이 남으면 수평 세열 지향성 지뢰를 쓰고 남지 않으면 기관총으로 끝내도록 한다. 수평 세열 지향성 지뢰를 쓰면 기관총과 달리 뒤에 2부터 ml까지 영향을 주지 못하기 때문에 cnt로 개수를.. 2023. 5. 12. [python] 백준 1464 뒤집기 3 https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문제 해결 간단해 보이지만 생각보다 간단하지 않은 문제 무조건 맨 왼쪽 문자부터 뒤집어야 한다는 규칙이 있다. 한 문자씩 왼쪽에서 오른쪽으로 볼 때 맨 뒤 혹은 맨 앞에 올 문자를 업데이트 한다고 보는 것이 편하다. 맨 앞에 올 수 있는 문자가 오면 그 앞에서 문자열 양 사이드 중 사전순으로 빠른 글자를 맨뒤로 오도록 뒤집은 다음 맨 앞에 올 수 있는 문자를 합하여 뒤집으면 된다. 사실 구현이 쉽지 않았.. 2023. 5. 11. [python] 백준 2109 순회강연 https://www.acmicpc.net/problem/2109 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불하겠다고 알려왔다. www.acmicpc.net 문제 해결 전형적인 그리디 문제 제안을 큰 p 순서, 작은 d 순서로 정렬을 시킨 다음 큰 p부터 최대한 늦게 스케줄이 비어 있는 날에 제안을 수락하려고 한다. 그러면 촉박한 d를 가진 것도 많이 할 수 있기 때문에 큰 값을 주는 순서대로 마감일자부터 가까운 날까지 확인하면서 계획이 없는 날에 강연을 하기로 하고 코드를 짜면 끝! CODE n = int(inpu.. 2023. 5. 8. [python] 백준 6198 옥상 정원 꾸미기 https://www.acmicpc.net/problem/6198 6198번: 옥상 정원 꾸미기 문제 도시에는 N개의 빌딩이 있다. 빌딩 관리인들은 매우 성실 하기 때문에, 다른 빌딩의 옥상 정원을 벤치마킹 하고 싶어한다. i번째 빌딩의 키가 hi이고, 모든 빌딩은 일렬로 서 있고 오른쪽으 www.acmicpc.net 문제 해결 stack 만으로 사용하기에는 시간초과가 걸려 dp를 이용함 for문을 통해 기준 빌딩을 잡은 가장 가까운 이전 빌딩부터 차례로 높이를 비교하여 더 큰 빌딩을 잡는다. 그 빌딩을 마지막으로 처음 빌딩부터 가장 긴 길이의 감소 수열 길이를 dp를 통해 저장한다. 그러면 기준 빌딩은 가장 긴 길이의 감소 수열 길이는 +1이고 그만큼의 정답이 늘어난다. 이것도 pypy3로는 통과 (p.. 2023. 4. 23. 이전 1 2 3 4 5 6 다음 728x90
