본문 바로가기
728x90

알고리즘316

[python] 백준 2636 치즈 https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 문제 해결 시간에 따라 치즈가 녹아서 없어지는 문제 → 시뮬레이션 가장자리는 치즈가 놓이지 않는다는 가정이 있으므로 그 중 하나인 (0,0)은 치즈가 없다. 치즈 안에 닫혀있는 공기는 상관x 따라서 치즈 밖에 있는 공기로 계속 퍼져나가고 치즈를 만나면 치즈를 녹인다.(그리고 더이상 그 지역에선 이동하지 않는다.) -> 이는 BFS를 통해 구현할 수 있다. 한 타임에 녹는 치즈의 개수를 세서 리스트에 저장한다. COD.. 2023. 4. 4.
[python] 백준 9466 텀 프로젝트 https://www.acmicpc.net/problem/9466 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 문제 해결 하나씩 돌아가며 그 안에 사이클이 있는지 확인한다. 사이클을 돌면서 한 번 지나간 index는 두 번 지나갈 필요가 없다.(만약 한 번 돌았을 때 사이클이 안만들어 졌으면 안만들어지는 것이다.) CODE import sys sys.setrecursionlimit(1000000) def cycle(num): global ans visited[num] = True c.append(num) new.. 2023. 4. 4.
[python] 백준 1826 연료 채우기 https://www.acmicpc.net/problem/1826 1826번: 연료 채우기 첫째 줄에 주유소의 개수 N(1 ≤ N ≤ 10,000)가 주어지고 두 번째 줄부터 N+1번째 줄 까지 주유소의 정보가 주어진다. 주유소의 정보는 두개의 정수 a,b로 이루어 져 있는데 a(1 ≤ a ≤ 1,000,000)는 성경 www.acmicpc.net 문제 해결 처음에 재귀(recursion)를 이용해 풀려고 했다. 하지만 모든 경우의 수를 다 찾아보는 것은 불필요하고 recursionError가 뜨게 되었다. 힙을 이용해 문제를 풀 수 있다고 하는데 어떻게 풀어야할지 몰랐다. 다른 분들의 풀이를 참고하여 풀 수 있게 되었다. 바로 계속 지나간다고 가정하고 만약 기름이 부족하게 되면 기름을 채우고 나서~채우.. 2023. 4. 4.
[python] 백준 17136 색종이 붙이기 https://www.acmicpc.net/problem/17136 17136번: 색종이 붙이기 과 같이 정사각형 모양을 한 다섯 종류의 색종이가 있다. 색종이의 크기는 1×1, 2×2, 3×3, 4×4, 5×5로 총 다섯 종류가 있으며, 각 종류의 색종이는 5개씩 가지고 있다. 색종이를 크 www.acmicpc.net 문제 해결 여러가지 경우의 수를 계산해야한다. 재귀함수를 통해 모든 경우의 수를 계산해서 최소의 값을 구할 수 있다. 각 크기의 색종이가 5개이므로 5개를 넘어가면 더이상 그 색종이를 사용하지 않는다. CODE import sys input = sys.stdin.readline INF= sys.maxsize def solve(x, y, cnt): global ans if y >= 10: .. 2023. 4. 3.
728x90