본문 바로가기

PS(Problem Solving)221

[백준] 19942번 - 다이어트 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 다이어트 https://www.acmicpc.net/problem/19942 19942번: 다이어트 식재료 N개 중에서 몇 개를 선택해서 이들의 영양분(단백질, 탄수화물, 지방, 비타민)이 일정 이상이 되어야 한다. 아래 표에 제시된 6가지의 식재료 중에서 몇 개를 선택해서 이들의 영양분의 각 www.acmicpc.net 맨 처음에 문제를 읽고 DP를 생각했으나, N이 15 이하인것을 보니 백트래킹으로 충분히 해결할 수 있었습니다. temp 벡터에 인덱스를 집어 넣어, res 벡터에 조건을 만족하는 인덱스 벡터를 넣어 정렬하여 출력합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/P.. 2022. 1. 16.
[백준] 2629번 - 양팔저울 (C++) 문제 및 풀이 문제) 백준 - 동적 계획법 - 양팔저울 https://www.acmicpc.net/problem/2629 2629번: 양팔저울 첫째 줄에는 추의 개수가 자연수로 주어진다. 추의 개수는 30 이하이다. 둘째 줄에는 추의 무게들이 자연수로 가벼운 것부터 차례로 주어진다. 같은 무게의 추가 여러 개 있을 수도 있다. 추의 무 www.acmicpc.net 추의 인덱스와 한쪽 저울에 올린 무게를 memoization을 적용하여 동적 계획법을 진행합니다. 추를 올릴 경우, 추를 올리지 않을 경우, 반대쪽에 올릴 경우를 생각하여 해결합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%201000~4999/26.. 2022. 1. 15.
[백준] 20365번 - 블로그2 (C++) 문제 및 풀이 문제) 백준 - Greedy - 블로그2 https://www.acmicpc.net/problem/20365 20365번: 블로그2 neighbor 블로그를 운영하는 일우는 매일 아침 풀고 싶은 문제를 미리 정해놓고 글을 올린다. 그리고 매일 밤 각각의 문제에 대하여, 해결한 경우 파란색, 해결하지 못한 경우 빨간색으로 칠한 www.acmicpc.net 주어진 문자열의 연속된 R, B를 하나로 줄인 후, 최소로 사용된 것을 선택하면 됩니다. C++ 소스코드) 2022. 1. 14.
[백준] 16432번 - 떡장수와 호랑이 (C++) 문제 및 풀이 문제) 백준 - DFS - 떡장수와 호랑이 https://www.acmicpc.net/problem/16432 16432번: 떡장수와 호랑이 동희가 N일동안 호랑이에게 떡을 줄 방법이 있다면 i (1 ≤ i ≤ N) 번째 줄에 동희가 호랑이에게 주어야 할 떡을 출력합니다. 이 떡은 동희가 i번째 날에 만든 떡이어야 합니다. 만약 동희가 떡을 www.acmicpc.net N일에 팔 수 있는 떡 K를 Bool 형태의 배열에 T[N][K]로 저장합니다. flag를 통해 방문 여부를 확인하며 DFS로 탐색합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2015000~19999/16432_%EB%96%A.. 2022. 1. 13.
[백준] 15658번 - 연산자 끼워넣기 (2) (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 연산자 끼워넣기(2) https://www.acmicpc.net/problem/15658 15658번: 연산자 끼워넣기 (2) 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1보다 크거나 같고, 4N보다 작거나 같은 4개의 정수가 주어지는데, 차례대 www.acmicpc.net 처음에 permutations를 활용하기 위해 파이썬으로 시도했다가 TLE로 틀려, C++을 통한 백트래킹으로 해결했습니다. 부분합, 인덱스, 4가지 연산자의 개수를 매개변수로 백트래킹을 적용합니다. C++ 소스코드) Full Code) https://github.com/Chocochip1.. 2022. 1. 13.
[백준] 10798번 - 세로읽기 (C++) 문제 및 풀이 문제) 백준 - 구현 - 세로읽기 https://www.acmicpc.net/problem/10798 10798번: 세로읽기 총 다섯줄의 입력이 주어진다. 각 줄에는 최소 1개, 최대 15개의 글자들이 빈칸 없이 연속으로 주어진다. 주어지는 글자는 영어 대문자 ‘A’부터 ‘Z’, 영어 소문자 ‘a’부터 ‘z’, 숫자 ‘0’ www.acmicpc.net 아주 쉬운 구현 문제였습니다. 배열을 모두 -1 초기화 후, 배열에 숫자가 들어간 것만 세로 방향으로 출력합니다. C++ 소스코드) 2022. 1. 13.
[백준] 7662번 - 이중 우선순위 큐 (C++) 문제 및 풀이 문제) 백준 - 우선순위 큐 - 이중 우선순위 큐 https://www.acmicpc.net/problem/7662 7662번: 이중 우선순위 큐 입력 데이터는 표준입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터의 첫째 줄에는 Q에 적 www.acmicpc.net C++의 multiset을 활용해 해결했습니다. multiset은 중복을 허용한 set으로서 삽입과 삭제를 O(logN)에 처리할 수 있습니다. multiset의 iterator를 사용하여 최대와 최소를 삭제합니다. C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/m.. 2022. 1. 12.
[백준] 20208번 - 진우의 민트초코우유 (C++) 문제 및 풀이 문제) 백준 - 백트래킹 - 진우의 민트초코우유 https://www.acmicpc.net/problem/20208 20208번: 진우의 민트초코우유 첫번째 줄에 민초마을의 크기인 N과 진우의 초기체력 M, 그리고 민트초코우유를 마실때 마다 증가하는 체력의 양 H가 공백을 두고 주어진다. N, M, H는 모두 10보다 작거나 같은 자연수이다. 두번째 www.acmicpc.net 민트초코우유의 개수가 10개 이하이며, 마을의 크기(N)이 10보다 작은 자연수이기에 백트래킹을 활용해 민트초코우유의 최대 개수를 구할 수 있습니다. 민트초코우유의 조표를 저장하는 mint 벡터와 visited를 통해 재귀적으로 백트래킹하며 해결할 수 있었습니다. C++ 소스코드) Full Code) https://github.c.. 2022. 1. 12.
[백준] 7569번 - 토마토 (C++) 문제 및 풀이 문제) 백준 - BFS - 토마토 https://www.acmicpc.net/problem/7569 7569번: 토마토 첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2 ≤ M ≤ 100, 2 ≤ N ≤ 100, www.acmicpc.net BFS를 통해 해결했습니다. Queue에 익은 토마토를 넣어주고 dist배열을 통해 방문 여부와 시간을 memo 합니다. 배열에 토마토 익힘 여부를 표시하여 BFS 종료 후, 안 익은 토마토가 있다면 -1을 출력하고 다 익었다면 dist 배열에서 최댓값을 출력합니다. C++ 소스 코드) Full Code) https://github.com/.. 2022. 1. 8.
반응형

티스토리툴바