본문 바로가기
728x90

그리디41

[python] 백준 14939 불 끄기 https://www.acmicpc.net/problem/14939 14939번: 불 끄기 전구 100개가 10×10 정사각형 모양으로 늘어서 있다. 전구에 달린 스위치를 누르면 그 전구와 위, 아래, 왼쪽, 오른쪽에 있는 전구의 상태도 바뀐다. 전구 100개의 상태가 주어지면 모든 전구를 끄 www.acmicpc.net 문제 해결 문제의 이해는 쉽지만 풀기 많이 어려웠던 문제 어디서부터 시작해야할지 많이 어렵다. 이 때 불 키고/끄고를 비트마스크를 이용해서 풀 수 있다고 하는데 어려워서 여러 코드를 확인하였다. 가장 중요한 것은 '첫 번째' 행의 불이 켜져있든 꺼져있든 스위치를 누루는 경우의 수를 모두 탐색하는 것이다. 이유는 첫 번째 행이 꺼져있어서 눌러 불을 켜도 다음 밑에 있는 스위치를 눌러서 다.. 2024. 3. 2.
[python] 백준 20310 타노스 문제 해결 Counter 함수를 통해 각각 몇 개씩 있는지 쉽게 알 수 있다. 문자열 처음부터 보면서 '0'은 Counter의 절반이 될 때 까지 만나면 정답 문자열에 넣는다. 문자열 처음부터 보면서 '1'은 Counter의 절반이 될 때 까지 만나면 패스한다. 문자열 처음부터 보면서 '1'은 Counter의 절반이 넘어가고 나서 만나면 정답 문자열에 넣는다. CODE import sys import math from collections import Counter input = sys.stdin.readline n = list(str(input()).strip()) X = Counter(n) a = X['0']//2 b = X['1']//2 answer = '' for i in range(len(n)).. 2023. 12. 23.
[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.
728x90