문제) 백준 - 백트래킹 - 진우의 민트초코우유
https://www.acmicpc.net/problem/20208
20208번: 진우의 민트초코우유
첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째
www.acmicpc.net
민트초코우유의 개수가 10개 이하이며, 마을의 크기(N)이 10보다 작은 자연수이기에 백트래킹을 활용해 민트초코우유의 최대 개수를 구할 수 있습니다. 민트초코우유의 조표를 저장하는 mint 벡터와 visited를 통해 재귀적으로 백트래킹하며 해결할 수 있었습니다.
C++ 소스코드)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
void dfs(int x, int y, int hp, int cnt) { | |
for (p next : mint) { | |
if (dist(x, y, next.first, next.second) <= hp && !visited[next.first][next.second]) { | |
visited[next.first][next.second] = true; | |
if(dist(hx, hy, next.first, next.second) <= hp - dist(x, y, next.first, next.second) + H) | |
ans = max(ans, cnt + 1); | |
dfs(next.first, next.second, hp - dist(x, y, next.first, next.second) + H, cnt + 1); | |
visited[next.first][next.second] = false; | |
} | |
} | |
} |
Full Code)
GitHub - Chocochip101/BOJ_Solution: BOJ Solutions
BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHub.
github.com
반응형
'PS(Problem Solving) > 백준_BOJ' 카테고리의 다른 글
[백준] 10798번 - 세로읽기 (C++) 문제 및 풀이 (0) | 2022.01.13 |
---|---|
[백준] 7662번 - 이중 우선순위 큐 (C++) 문제 및 풀이 (0) | 2022.01.12 |
[백준] 7569번 - 토마토 (C++) 문제 및 풀이 (0) | 2022.01.08 |
[백준] 6593번 - 상범 빌딩 (C++) 문제 및 풀이 (0) | 2022.01.06 |
[백준] 13023번 - ABCDE (C++) (0) | 2022.01.05 |
댓글