본문 바로가기
728x90

알고리즘/[python] 백준 BOJ328

[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.
[python] 백준 1464 뒤집기 3 https://www.acmicpc.net/problem/1464 1464번: 뒤집기 3 세준이는 어떤 문자열 S를 뒤집으려고 한다. 문자열을 뒤집는 방법은 문자열의 길이를 N이라고 하자. i만큼을 뒤집는다는 소리는 그 문자열의 처음부터 정확하게 i개의 문자를 역순으로 뒤집는 www.acmicpc.net 문제 해결 간단해 보이지만 생각보다 간단하지 않은 문제 무조건 맨 왼쪽 문자부터 뒤집어야 한다는 규칙이 있다. 한 문자씩 왼쪽에서 오른쪽으로 볼 때 맨 뒤 혹은 맨 앞에 올 문자를 업데이트 한다고 보는 것이 편하다. 맨 앞에 올 수 있는 문자가 오면 그 앞에서 문자열 양 사이드 중 사전순으로 빠른 글자를 맨뒤로 오도록 뒤집은 다음 맨 앞에 올 수 있는 문자를 합하여 뒤집으면 된다. 사실 구현이 쉽지 않았.. 2023. 5. 11.
[python] 백준 1398 동전 문제 https://www.acmicpc.net/problem/1398 1398번: 동전 문제 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 초콜릿의 가격이 주어진다. 가격의 1015보다 작거나 같은 자연수이다. www.acmicpc.net 문제 해결 동전이 1, 10, 25... 패틴을 확인 할 수 있는지 문제이다. 동전의 수열 집합을 A라 할 때 $A_{i}$ = 100$A_{i-3}$ 임을 확인 할 수 있으면 문제는 쉬워진다. 100 단위로 동전을 최대한 적은 수로 처리하는 방법을 생각하면 된다. CODE t = int(input()) coins = [1, 10, 25] # 이 형태로 계속 간다. for _ in range(t): x = int(input()) answer = .. 2023. 5. 10.
728x90