본문 바로가기
반응형

백준45

BOJ 14888 - 연산자 끼워넣기 / C++ 문제 링크 : https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 풀이 주석으로 대체 코드 #include #include #include using namespace std; int n, maxVal = -2e9, minVal = 2e9; vector nums; int opers[4]; //덧셈, 뺄셈, 곱셈, 나눗셈 순서 void DFS(int sum, int idx){ if(idx == .. 2022. 3. 28.
BOJ 1913 - 달팽이 / C++ 문제 링크 : https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 풀이 우선, 구현에 쓰인 변수는 크게 3가지이다. 좌표(x, y) / 방향(goDown,Right,Up,Left) / 라운드(r) 이다. 달팽이의 구현을 보면 (0, 0)에서 n^2부터 시작하여 하-우-상-좌 순서로 돌게 된다. 또한, 배열을 벗어나면 안되기 때문에 각 좌표는 n을 벗어나거나 0보다 작아지면 안된다. 하지만 왼쪽으로 갈 때를 보면 0보다 작아지는 것이 아니라 1보다 작.. 2022. 3. 22.
BOJ 4486 - 녹색 옷 입은 애가 젤다지? / C++ 문제 링크 : https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 풀이 다익스트라와 BFS가 섞인 문제이다. 현재 노드에서 이동할 수 있는 경우는 우, 하, 상, 좌 순서로 한칸 씩이다. 먼저, 다익스트라 알고리즘처럼 dist 배열을 모두 INF로 초기화 시킨 뒤 (0, 0)에서 출발한다. 정점을 탐색하며 dist 배열을 업데이트할 수 있다면 업데이트한 뒤 해당 정점으로 이동한다. dist 배열이 모두 업데이트 되었으면 (n-1,.. 2022. 3. 20.
BOJ 1238 - 파티 / C++ 문제 링크 : https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 풀이 먼저 X 노드에서 다른 모든 노드들간의 거리를 구한다. 다음으로, 1부터 n번 노드까지 모두 다익스트라를 수행한다. 노드의 개수가 최대 1000개이므로 우선순위 큐로 구현하였다면 시간 초과가 나지 않는다. i번 노드에서 X번 노드까지의 거리를 임시 변수 tmp에 더하고 X번 노드에서 i번 노드까지의 거리도 tmp에 더하면 왕복 거리가 완성되고 이를.. 2022. 3. 20.
반응형

티스토리툴바