본문 바로가기
728x90

정렬34

[python] 백준 13904 과제 https://www.acmicpc.net/problem/13904 13904번: 과제 예제에서 다섯 번째, 네 번째, 두 번째, 첫 번째, 일곱 번째 과제 순으로 수행하고, 세 번째, 여섯 번째 과제를 포기하면 185점을 얻을 수 있다. www.acmicpc.net 문제 해결 어떻게 일을 먼저 계획할 것인지 순서를 정하는 문제 당연히 점수가 높은 일을 먼저 계획을 해야한다.(중요하기 때문) 그다음 고려할 것은 가능하면 빨리 해결해야하는 문제이다. 따라서 힙(heap)을 사용할 것이다. 그리고 가능하면 마감기간에 처리를 하여 비록 비중이 적지만 빨리 처리해야하는 것도 처리할 수 있도록 한다. CODE import sys input = sys.stdin.readline import heapq def sol.. 2023. 12. 14.
[python] 백준 3043 장난감 탱크 https://www.acmicpc.net/problem/3043 3043번: 장난감 탱크 상근이는 생일 선물로 장난감 탱크 N개를 받았다. 탱크를 가지고 놀기 전장을 만들었다. 전장은 나무판 위에 N행 N열 크기로 만들었다. 각 탱크가 한 번에 움직일 수 칸은 인접한 네 칸이다. 탱크 www.acmicpc.net 문제 해결 N행 N열 크기의 나무판이므로 각 행마다 하나의 탱크가 들어가고 각 열마다 하나의 탱크가 들어가야 한다는 것은 쉽게 알 수 있다. 문제는 겹치지 않고 어떻게 순서를 정해서 이동시킬 것이며 어떤 기준으로 이동시킬 것이냐가 문제이다. 어동 시키는 방법은 간단하다. 행을 기준으로 각 탱크의 위치를 정렬시킨다. 그 다음 맨 위에 행부터 아래행으로 내려가면서 1행, 2행, 3행 . . .에 .. 2023. 11. 10.
[python] 백준 2659 십자카드 문제 https://www.acmicpc.net/problem/2659 2659번: 십자카드 문제 입력은 한 줄로 이루어지며, 이 한 줄은 카드의 네 모서리에 씌여있는 1 이상 9 이하의 숫자 4개가 시계 방향으로 입력된다. 각 숫자 사이에는 빈칸이 하나 있다. www.acmicpc.net 문제 해결 주어진 입력값을 가지고 시계수를 구하는 함수를 만든다. 그 방법은 맨 앞의 숫자를 맨 뒤로 옮겨가며 가장 최솟값이 나오는 수를 구하면 된다. 1111은 가장 작은 시계수인 것은 명백하다. x를 입력값을 십자모형의 카드에 넣어 얻은 시계수라고 하면 1111부터 x까지 시계수의 개수를 구하면 되는 문제이다. CODE import sys input = sys.stdin.readline def clock_num(n): .. 2023. 10. 18.
[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.
728x90