개발자 꿈나무 개발자 꿈나무

오늘은 백준 7569번 토마토 문제를 풀어보았어요. 백준에 토마토 문제가 하나 더 있는데, 그 문제는 2차원 상자이고, 이 문제는 3차원 상자의 탐색이라는 점에서 난이도가 조금 더 높다고 볼 수 있겠네요. www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net 먼저 이 문제를 풀기 위해서 bfs로 접근을 해보았는데요, 토마토의 상태를 저장할 상자의 3차원 배열을 설정하고, 익은 토마토(1)들을 queue에 넣어 그 때부터 bfs를 해주며 하루..

이번에 풀어본 문제는 "백준: 동물원(1309)"입니다. 문제를 읽어보면 직관적으로 dp문제라는 것을 알 수 있었습니다. 그렇다면 문제 풀이의 핵심은 다름 아닌 핵심 규칙(점화식)을 찾는 것인데요, 문제에서 주어진 규칙을 보면 열은 2열로 고정되어 있고, 행(n)이 주어지는 형태입니다. 그렇다면 한 행이 늘어날 때마다의 규칙을 찾아서 점화식을 세워주면 되겠네요. 점화식을 세우기 전, 1) 가로로 사자를 배치하면 안 된다. 2) 세로로 사자를 배치하면 안 된다. 3) 사자를 배치하지 않는 경우도 한 가지 경우로 친다. 이 세 가지 조건을 생각해야 합니다. 따라서 위 조건들에 따라서 dpLi[n][0]을 n행에 사자를 아예 배치하지 않는 경우, dpLi[n][1]을 n행의 왼쪽에만 사자를 배치할 경우, dp..