🥇 Problem Solving

[Python] BOJ / 17144번 / 미세먼지 안녕!

17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 📝 풀이 T초 동안 미세먼지의 확산과 순환이 반복적으로 일어나며 T초가 지난 후에 방에 남아있는 미세먼지의 양을 출력하는 문제 미세먼지 확산 알고리즘의 경우 확산과 동시에 원래 해당 칸에 있던 값이 덮어씌워지는 것을 방지하기 위해 임시로 리스트를 하나 더 생성하여 구현하였음 미세먼지 순환 알고리즘의 경우 공기청정기에 따른 순환 방향을 미리 정의해놓고 하나의 함수를 통해 해당 방향에 따라 미세먼지가 순환할 수 있도록 구현하였음 💻 소스코드 import sys sy..

[Python] BOJ / 1038번 / 감소하는 수

1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 📝 풀이 백트리킹 알고리즘 사용 재귀로 구현할 경우 메모리 초과가 발생하므로 while문을 통해 구현 알고리즘 현재 값이 감소하는 수라면 현재 값에 +1을 수행 현재 값이 감소하는 수가 아니라면 현재 값과 가장 가까운 감소하는 수가 되도록 수정 위 과정을 반복하며 N번째 감소하는 수가 되었을 때의 값을 출력 N번째 감소하는 수가 없는 경우에는 -1을 출력해야하며 ,이는 최대 감소하는 수인 '9876543210'보다 현재 값이 클 경우임 💻 소스코드..

[Python] BOJ / 9466번 / 텀 프로젝트

9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 📝 풀이 팀이 만들어지기 위해선 사이클의 마지막 학생이 선택한 학생이 첫 번째 학생과 같아야 한다. 즉, 첫과 끝이 이어진 순환 사이클이 형성되어야 한다. result += cycle[cycle.index(arr[x]):] 위 연산을 통해 순환 사이클이 형성되는 구간부터만 팀을 구성시킬 수 있다. 💻 소스 코드 import sys input = sys.stdin.readline sys.setrecursionlimit(10 ** 6) def dfs(x): global ..

[Python] BOJ / 3055번 / 탈출

3055번: 탈출 사악한 암흑의 군주 이민혁은 드디어 마법 구슬을 손에 넣었고, 그 능력을 실험해보기 위해 근처의 티떱숲에 홍수를 일으키려고 한다. 이 숲에는 고슴도치가 한 마리 살고 있다. 고슴도치는 제 www.acmicpc.net 📝 풀이 고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다. 즉, 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다. 물이 차 있는 곳 먼저 각각 큐에 저장하고 BFS를 수행하기 직전에 고슴도치의 위치를 큐에 저장함으로써 물이 먼저 확장되고 나서 고슴도치가 이동하는 식으로 구현 큐에는 (y좌표, x좌표, 타입, 시간) 값이 들어감 타입 값은 현재 이동중인 개체(고슴도치 또는 물)를 나타냄 시간 값은 현재 좌표까지 이동하는데 걸리는 시간을 나타냄 💻 소스코드 im..