본문 바로가기

PS(Problem Solving)/백준_BOJ201

[백준] 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.
[백준] 6593번 - 상범 빌딩 (C++) 문제 및 풀이 문제) 백준 - BFS - 상범빌딩 https://www.acmicpc.net/problem/6593 6593번: 상범 빌딩 당신은 상범 빌딩에 갇히고 말았다. 여기서 탈출하는 가장 빠른 길은 무엇일까? 상범 빌딩은 각 변의 길이가 1인 정육면체(단위 정육면체)로 이루어져있다. 각 정육면체는 금으로 이루어져 있어 www.acmicpc.net 3차원 미로를 탈출할 수 있는 최단 시간을 찾는 문제였습니다. 그래프 탐색에서 최단 시간을 찾을 때, 간선의 비용이 같으면 BFS를 사용합니다. 기본적인 3차원 BFS를 연습하기에 좋은 문제였습니다. C++ 소스 코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%205000~99.. 2022. 1. 6.
[백준] 13023번 - ABCDE (C++) 문제) 백준 - DFS - ABCDE https://www.acmicpc.net/problem/13023 13023번: ABCDE 문제의 조건에 맞는 A, B, C, D, E가 존재하면 1을 없으면 0을 출력한다. www.acmicpc.net C++ 소스코드) Full Code) https://github.com/Chocochip101/BOJ_Solution/blob/main/Problem%2010000~14999/13023_ABCDE.cpp GitHub - Chocochip101/BOJ_Solution: BOJ Solutions BOJ Solutions. Contribute to Chocochip101/BOJ_Solution development by creating an account on GitHu.. 2022. 1. 5.
[백준] 1956번 - 운동 (C++) 문제 및 풀이 문제) 백준 - 플루이드 와샬 - 운동 https://www.acmicpc.net/problem/1956 1956번: 운동 첫째 줄에 V와 E가 빈칸을 사이에 두고 주어진다. (2 ≤ V ≤ 400, 0 ≤ E ≤ V(V-1)) 다음 E개의 줄에는 각각 세 개의 정수 a, b, c가 주어진다. a번 마을에서 b번 마을로 가는 거리가 c인 도로가 있다는 의 www.acmicpc.net 마을의 개수(V=400)가 충분히 작기 때문에 플루이드 와샬로 최단 거리를 구할 수 있었습니다. 사이클 여부는 최단거리를 구한 후 board [i][j]와 board [j][i]가 존재하면 사이클이 존재하는 것으로 판단하면 됩니다. C++ 소스 코드) Full Code) https://github.com/Chocochip10.. 2022. 1. 5.
반응형

티스토리툴바