728x90 투포인터14 [python] 백준 17609 회문 https://www.acmicpc.net/problem/17609 17609번: 회문 각 문자열이 회문인지, 유사 회문인지, 둘 모두 해당되지 않는지를 판단하여 회문이면 0, 유사 회문이면 1, 둘 모두 아니면 2를 순서대로 한 줄에 하나씩 출력한다. www.acmicpc.net 문제 해결 양쪽 끝 start = 0 , end = len(word)-1로 시직해서 투포인터로 양쪽 대칭을 확인하는 문제 만약 대칭이 안되는 부분이 있다면 양쪽 중 한 문자를 없앴을 때 대칭이 되는지 확인 주의할 점은 대칭이 안되는 부분이 abca와 같이 붙어있는 경우가 있으므로 start 2023. 4. 23. [python] 백준 3649 로봇 프로젝트 https://www.acmicpc.net/problem/3649 3649번: 로봇 프로젝트 각 테스트 케이스마다 한 줄에 하나씩, 구멍을 완벽하게 막을 수 있는 두 조각이 없다면 'danger'를 출력한다. 막을 수 있는 경우에는 'yes ℓ1 ℓ2'를 출력한다. (ℓ1 ≤ ℓ2) 정답이 여러 개인 경우에 www.acmicpc.net 문제 해결 전형적인 투포인터 문제 n==0일 때와 n==1일 때 불가능하므로 danger 출력하고 다음 테스트케이스 출력 n>=2일 때부터 올림차순으로 정렬된 리스트에서 start =0 end = n-1을 잡고 두 원소의 합이 x가 될 때까지 숫자를 조절하여 찾는다. start>=end가 되면 찾을 수 없는 것이므로 danger 출력하고 다음 테스트 케이스 출력 CODE .. 2023. 4. 22. [python] 백준 2343 기타 레슨 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 해결 블루레이 크기란 무엇인가? => 컴퓨터 메모리로 생각하면 편하다. ex) 블루레이 크기 17이면 수의 합이 17이 될 때 까지만 메모리 저장 가능 메모리 크기는 강의 길이가 가장 큰거 이상이여야 한다. 메모리 크기는 모든 강의 길의 합 이하여야 한다. 따라서 메모리 크기의 최소지점과 최대지점 투 포인터를 집아 이분 탐색을 해서 블루레이 크기중 최소를 출력하도록 한다. CODE import sy.. 2023. 2. 23. [python] 백준 1253 좋다 https://www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 문제 해결 리스트 안의 서로 다른 두 수의 합이 리스트 안의 다른 수가 되는 경우의 수를 구하는 문제이다. 리스트 안의 서로 다른 두 수의 합을 비교하는 것이므로 리스트를 올림차순으로 정렬하고 투포인터 이용하는 것이 좋아 보인다. 두 수의 합이 리스트 안에 있어도 3 + 0 = 3 등 다른 수가 되지 않으면 그 경우는 경우의 수로 계산하지 않는다. CODE import sys input = sys.stdin.readline .. 2023. 2. 18. 이전 1 2 3 4 다음 728x90
