본문 바로가기

PS(Problem Solving)221

[백준] 5014번 - 스타트링크 (C++) 문제 및 풀이 문제) 백준 - BFS - 스타트링크 https://www.acmicpc.net/problem/5014 5014번: 스타트링크 첫째 줄에 F, S, G, U, D가 주어진다. (1 ≤ S, G ≤ F ≤ 1000000, 0 ≤ U, D ≤ 1000000) 건물은 1층부터 시작하고, 가장 높은 층은 F층이다. www.acmicpc.net BFS를 통해서 G층까지 최소 버튼 횟수를 구한다. 핵심은 Queue에 방문 층과 버튼 횟수를 함께 넣는 것. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/5014_%EC%8A%A4%ED%83%80%ED%8A%B8%EB%A7%81%ED%81%AC... 2021. 11. 9.
[백준] 9372번 - 상근이의 여행 (C++) 문제 및 풀이 문제) 백준 - BFS - 상근이의 여행 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 어떤 그래프로든 풀이가 가능하다. bfs가 제일 편해서 구현했다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9372_%EC%83%81%EA%B7%BC%EC%9D%B4%EC%9D%98%20%E.. 2021. 11. 7.
[백준] 7579번 - 앱 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 앱 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 메모리를 memoization을 진행하면 메모리 초과로 터진다. dp[idx][Cost]: Cost로 idx번째 앱에서 얻을 수 있는 최대 메모리를 계산한다. Cost를 0부터 증가시켜 M보다 클 경우 break 하여 출력한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main.. 2021. 11. 7.
[백준] 12852번 - 1로 만들기 2 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 1로 만들기 2 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net Top-Down 방식으로 해결했다. 1로 만들수 있는 모든 경우를 memoiztion을 진행하면서 trace에도 memo를 진행한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/12852_1%EB%A1%9C%20%EB%A7%8C%EB%93%A4%EA%B8%B0%202.cpp GitHub - Chocochip101/BO.. 2021. 11. 6.
[백준] 11060번 - 점프 점프 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 점프 점프 https://www.acmicpc.net/problem/11060 11060번: 점프 점프 재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 www.acmicpc.net cache[idx]: idx에서 n-1번 칸까지 갈 수 있는 최소 점프 횟수. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/11060_%EC%A0%90%ED%94%84%20%EC%A0%90%ED%94%84.c.. 2021. 11. 4.
[백준] 9507번 - Generations of Tribbles (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - Generations of Tribbles https://www.acmicpc.net/problem/9507 9507번: Generations of Tribbles 꿍은 군대에서 진짜 할짓이 없다. 그래서 꿍만의 피보나치를 만들어보려고 한다. 기존의 피보나치는 너무 단순해서 꿍은 좀더 복잡한 피보나치를 만들어보고자 한다. 그래서 다음과 같은 피보 www.acmicpc.net n이 3 이하 일 경우의 기저 사례 처리와 점화식을 이용해 memoization을 적용한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~9999/9507_Generations%.. 2021. 11. 3.
[백준] 14728번 - 벼락치기 (C++) 문제 및 풀이 문제) 백준 - DP(동적 계획법) - 벼락치기 https://www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 한정된 시간에 최대 점수를 내기 위해 선택해야하는 전형적인 냅색(배낭) 문제. DP(인덱스, 남은 공부 시간)으로 해결할 수 있다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999.. 2021. 11. 2.
[백준] 13565번 - 침투 (C++) 문제 및 풀이 문제) 백준 - DFS - 침투 https://www.acmicpc.net/problem/13565 13565번: 침투 첫째 줄에는 격자의 크기를 나타내는 M (2 ≤ M ≤ 1,000) 과 N (2 ≤ N ≤ 1,000) 이 주어진다. M줄에 걸쳐서, N개의 0 또는 1 이 공백 없이 주어진다. 0은 전류가 잘 통하는 흰색, 1은 전류가 통하지 않 www.acmicpc.net dfs를 통해서 visited 배열을 갱신 후, inner side에 도달했는지 확인한다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/13565_%EC%B9%A8%ED%88%AC.cpp GitHub .. 2021. 11. 1.
[백준] 14890번 - 경사로 (C++) 문제 및 풀이 문제) 백준 - 구현 - 경사로 https://www.acmicpc.net/problem/14890 14890번: 경사로 첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다. www.acmicpc.net 각 행, 열마다 경사로를 놓을 수 있는지 확인한다. board: 지도 visited: 경사로 존재 여부 canGo: 해당 열(행) 통과 여부 C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/14890_%EA%B2%BD%EC%82%AC%EB%A1%9C.cpp Git.. 2021. 10. 31.
반응형

티스토리툴바