본문 바로가기
728x90

투포인터14

[python] 백준 7795 먹을 것인가 먹힐 것인가 https://www.acmicpc.net/problem/7795 7795번: 먹을 것인가 먹힐 것인가 심해에는 두 종류의 생명체 A와 B가 존재한다. A는 B를 먹는다. A는 자기보다 크기가 작은 먹이만 먹을 수 있다. 예를 들어, A의 크기가 {8, 1, 7, 3, 1}이고, B의 크기가 {3, 6, 1}인 경우에 A가 B를 먹을 www.acmicpc.net 문제 해결 모든 원소를 1대1로 비교해서 계산하는 것은 너무 비효율적이라는 생각이 든다. 정렬을 이용해서 A와 B를 오름차순으로 정렬하고, $i \in {0,1,2,3, . . .n-1} $ $j \in {0,1,2,3, .. m-1}$ 인 임의의 $i, j$에 대해서 A[i] > B[j]이면 A[i+1] > B[j]임을 생각을 하면 좋다. 만약.. 2023. 9. 14.
[python] 백준 2283 구간 자르기 https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 문제 해결 리스트 인덱스를 x좌표로 하여 막대의 좌표 ( ex: (3,7)이면 vertical[3:7]에 +1씩 더해서 길이를 측정할 수 있도록 한다.)로 나타낸다. 원하는 만큼의 길이(k)가 안나오면 끝점(r)를 1씩 높여서 해당되는 길이만큼 증가시키고 그보다 크게 나오면 시작점(l)를 1씩 높여서 해당되는 길이만큼 줄이면서 원하는 값이 나오는.. 2023. 6. 26.
[python] 백준 2923 숫자 게임 https://www.acmicpc.net/problem/2923 2923번: 숫자 게임 창영이와 현우는 새로운 게임을 하고 있다. 이 게임은 여러 라운드로 이루어져 있다. 매 라운드가 시작할 때, 현우는 창영이에게 100보다 작은 두 숫자 A와 B를 말해준다. 그러고 난 뒤, 창영이는 www.acmicpc.net 문제 해결 n번 숫자 쌍이 추가 될 때마다 A와 B의 원소를 쌍을 맞춰 각 쌍의 최댓값의 최솟값을 구하는 문제 쉽게 직관적으로 A의 오름차순 수열 $a_{1}$, $a_{2}$ , ... 라 하고 B의 내림 차순 수열 $b_{1}$, $b_{2}$, ..라 할 때 answer = min($a_{i}+b_{i}$) 가 될 것이다. 그러므로 각 숫자의 개수를 인지한 다음 하나씩 짝을 맞추었을 때 .. 2023. 5. 16.
[python] 백준 2831 댄스 파티 https://www.acmicpc.net/problem/2831 2831번: 댄스 파티 남자 N명과 여자 N명이 상근이가 주최한 댄스 파티에 왔다. 상근이는 모든 사람의 키를 알고있다. 각 남자는 모두 여자와 춤을 출 수 있고, 여자는 남자와 춤을 출 수 있다. 모든 사람은 많아야 한 www.acmicpc.net 문제 해결 음수-양수, 양수-음수만 짝이 가능하다. 음수쪽 절대값이 더 커야한다. sort()를 통해 수를 배열하고 음수인 부분이 더 클 경우에 짝을 만들어준다. 남자는 가장 작은수부터, 여자는 가장 큰 수부터 시작해서 짝을 맞춰본다.(절대값이 큰것끼리 짝을 맞춰야 더 많이 짝을 만들 수 있다.) CODE n = int(input()) M = list(map(int, input().split(.. 2023. 5. 6.
728x90