본문 바로가기
728x90

그리디41

[python] 백준 1201 NMK https://www.acmicpc.net/problem/1201 1201번: NMK 첫째 줄에 세 정수 N, M, K가 주어진다. www.acmicpc.net 문제 해결 먼저 수열을 구할 수 있기 위한 n의 범위를 알아야한다. m+k-1 ≤ n ≤ m*k 이다. n이 가장 작을 때는 [1, 2, 3, .. . m, m-1, m-2, . . . m+k-1] 수열이며 n이 가장 클 때는 [k,k-1,k-2, . . . 1, 2*k, 2*k-1, . . . k+1, . . . m*k, m*k-1, . . . (m-1)*k + 1] 이다. n이 범위 안에 들어오면 처음으로 k개의 숫자를 내림차순해서 k개의 내림차순을 만든다. 이제 k+1~n까지 정렬해서 m-1개의 오름차순 수열을 만들어야한다. 여기서부터 너무.. 2023. 8. 27.
[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] 백준 1736 쓰레기 치우기 https://www.acmicpc.net/problem/1736 1736번: 쓰레기 치우기 방은 세로 N, 가로 M (1 ≤ N, M ≤ 100) 크기의 격자 판으로 표현할 수 있다. 왼쪽 위의 위치를 (0, 0)이라 하고, 오른쪽 아래를 (N - 1, M - 1)이라고 하자. 이 판의 몇몇 칸에는 쓰레기가 놓여 있다. 쓰레 www.acmicpc.net 문제 해결 N*M행렬 중 행렬 값이 1인 행,열을 0으로 바꾸는 과정이라고 생각하면 된다. 그렇지만 움직이는 방향은 →,↓ 두 가지로 생각하면 된다. 재귀를 이용해서 1인 행렬값을 0으로 만들어가며 영행렬을 만들 수 있다. 깊이 너비 탐색(dfs)를 최소한으로 했을 때의 개수를 구하면 될 것이다. 사실 아이디어를 생각하기 너무 어려웠고 아이디어를 참고를.. 2023. 5. 13.
[python] 백준 19644 좀비 떼가 기관총 진지에도 오다니 https://www.acmicpc.net/problem/19644 19644번: 좀비 떼가 기관총 진지에도 오다니 킬로와 헥토는 좀비 떼로부터 탄약고를 사수하는 데에 성공했다. 포상 휴가나 조기 전역을 기대했으나 좀비 사태로 인해 계엄령이 선포되면서 오히려 전역이 연기되고 기관총 진지에 배치되었 www.acmicpc.net 문제해결 시물레이션 같은 문제이지만 시물레이션으로 생각하고 구현하면 시간초과가 나기 쉽다. (O(n))으로 풀어야 한다. 기관총이 1부터 ml까지 영향을 주기 때문에 기관총에 영향을 받았을 때 체력이 남으면 수평 세열 지향성 지뢰를 쓰고 남지 않으면 기관총으로 끝내도록 한다. 수평 세열 지향성 지뢰를 쓰면 기관총과 달리 뒤에 2부터 ml까지 영향을 주지 못하기 때문에 cnt로 개수를.. 2023. 5. 12.
728x90