기록(記錄)

본문 바로가기

알고리즘

백준 문제 풀이 [Python] 26076번 곰곰이의 식단 관리 2 https://www.acmicpc.net/problem/26076 25/09/12 0-1 BFS문제다. 이전에 곰곰컵에 나가서 틀린 이후에 한참동안 묵혀놨다가 해결해서 적어본다. 문제 접근 방식: 2025.09.15 - [알고리즘/백준 문제 풀이] - [Python] 3140번 GULIVER [Python] 3140번 GULIVERhttps://www.acmicpc.net/problem/3140 25/09/03 재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다. 문제 접근 방식: 두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값lighter.tistory.com기본적인 접근 방식은 위의 문제와 매우매우매우 유사하다. 단지 해당 문제는 정답이 0, 1, 2로..
백준 문제 풀이 [Python] 3140번 GULIVER https://www.acmicpc.net/problem/3140 25/09/03 재밌는 0-1 BFS문제이다. 해당 아이디어를 통해 다른 문제도 쉽게 해결할 수 있었다. 문제 접근 방식: 두 조각으로 분리하기 위해서 필요한 벽의 개수의 최솟값을 묻는 문제이다. 처음에 생각했던 방법은 왼쪽에서 오른쪽으로 순회하면서 진행하는 2차원 DP였다. $DP[r][c]$ $=$ $r$행 $c$열까지 봤을 때 두 조각으로 분리하기 위해 필요한 벽의 개수의 최솟값 으로 DP식을 정의하고 돌렸다. 당연히 틀렸다. 틀린 후에는 태그를 까고 0-1 BFS라는 사실을 알게된 후에, 벽일 때는 0의 코스트로 가고 벽이 아닐 때는 1의 코스트로 가서 왼쪽에서 오른쪽으로 순회하도록 짰다. 근데 틀렸다. 진행방향을 오른쪽 위, ..
백준 문제 풀이 [Python] 12944번 재미있는 숫자 놀이 https://www.acmicpc.net/problem/12944 25/09/14 전형적인 포함-배제 원리의 문제이다. 문제 접근 방식: 당신은 포함배제의 원리를 아는가? $K$개 중 $m$개를 선택해서 $N$에 $m$개의 숫자의 $\text{lcm}$을 나눠준 값을 더하거나 빼주면 된다. $m$이 홀수인 경우 더해주고, $m$이 짝수인 경우 빼주면 된다. 왜 그런지는 집합의 모습을 생각해보면 이해하기 쉬울 것이다. 아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.더보기# 12944번 재미있는 숫자 놀이# 수학, 포함 배제의 원리import sysinput = sys.stdin.readlinefrom math import lcmans = 0N, K = m..

수학

회고록

감상록

티스토리툴바