나쿠리 개발 메모장

개요 https://www.acmicpc.net/problem/13016 13016번: 내 왼손에는 흑염룡이 잠들어 있다 첫째 줄에 국가의 수 N(2 ≤ N ≤ 50,000)이 주어진다. 둘째 줄부터 N-1개의 줄에 도로의 정보가 주어진다. 각 도로의 정보는 from, to, length 으로 이루어져 있으며, 이 도로는 국가 from과 국가 to를 연결 www.acmicpc.net PlatinumV 문제 제목이 왜 이래 풀기 전, 선행하면 좋은 문제 1667번: 트리의 지름 풀이 대충 요약하자면 , , 가중치가 있는 트리의 모든 노드에서 가장 먼 노드까지의 거리를 출력하면 된다. N maxSum) { maxSum = distSum; startNode = idx; } result[idx] = max(re..

개요 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 골드 5 문제다. 풀이 완전 0-1 배낭 알고리즘의 정석 문제다. DP 테이블을 활용, , , 항상 느끼는 부분이지만 과거에 한번 접해봤던 건 다시 하면 잘되는 경향이 있는 것 같다. 몇 개월 전에는 잘 이해가 되지 않았는데, 다시 보니 어렵지 않다,,~ 코드 #include using namespace std; int N, ..

개요 https://www.acmicpc.net/status?from_mine=1&problem_id=2564&user_id=ccmuk58 채점 현황 www.acmicpc.net 실버1 짜리 문제다. 풀이 그냥 간단한 구현 문제다 싶었는데 생각보다 까다로웠다. 일단 방향하고 이동 값이 입력으로 들어왔고, 편의를 위해 좌표 형태(x,y)로 변환했다. 이후 재귀 형태로 탐색했다. 실버 맞아?? 완전 힘숨실 코드 #include using namespace std; constexpr int LIMIT = 102; using pInt = pair; bool isWest(const pInt& curX, const pInt& length); bool isNorth(const pInt& curX, const pInt..

개요 https://www.acmicpc.net/problem/7490 7490번: 0 만들기 각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다. www.acmicpc.net 골드5 난이도 문제 풀이 단순한 구현 문제인듯했다. 처음에 '+' '-' 입력만 보고 왜 골드지 싶었는데 ,, 공백 입력이 있었다. 재귀로 문자열을 합쳐가며 답을 구했다. 코드 #include using namespace std; void recursiveSearch(int N, int currentN = 1, string expression = "1"); int getSum(string expressionStr); int convertOper..

개요 https://www.acmicpc.net/problem/16990 16990번: 마법 장벽 예제를 그림으로 표현하면 다음과 같다. 회색 칸들 중 수가 쓰인 곳들에 마법 대포가 있고, 그 수의 방향으로 포탄을 쏜다. 아래의 세 줄은 위에서부터 각각 1, 2, 3번째 막을 나타낸다. 1~4번째 www.acmicpc.net 플레티넘4 난이도의 태그가 없는(?) 문제 지인의 재밌다는 추천에 몇 시간 잡고 풀어냈다. 선수 지식 없고 재밌는 문제,. 강추!! 풀이 입력을 보면 알겠지만 N M; for (int i = 0; i > L >> pattern; for (int k = 0; k < LENGTH; k += pattern.length()) { for (int j = 0; j..

개요 https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 풀이 DP 문제 몇 개 풀다보니까 이정도는 이제 어느정도 보이는 것 같다. 현재 가격은 이전 누적 가격 중 가능한 가장 저렴한 가격 + 현재 집 가격이다. 3가지 색상의 가격을 비교하며 모든 집을 채워 넣다보면 마지막 3가지 경우 중 작은 값이 정답이 된다. 코드 #include #include #include using namespace std; int main() {..

개요 https://www.acmicpc.net/problem/4811 4811번: 알약 입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다. 입력의 마지막 줄에는 0이 하나 주어진다. www.acmicpc.net 골드5 짜리 DP문제다. 풀이 W는 일반 알약, H가 반쪽짜리 알약이다. 2차원 배열의 형태로 생각을 해보았는데, 보면 반복적인 형태가 보인다. W와 H가 공존할 때 경우의 수가 증가하는 규칙이 있다. 위 과정을 통해 점화식을 구했고 재귀(Top-Down)로 구현했다. 코드 #include #include using namespace std; long long dp[31][31]; long long GetC..

개요 https://www.acmicpc.net/problem/2302 2302번: 극장 좌석 주어진 조건을 만족하면서 사람들이 좌석에 앉을 수 있는 방법의 가짓수를 출력한다. 방법의 가짓수는 2,000,000,000을 넘지 않는다. (2,000,000,000 sync_with_stdio(0); int dp[41] = { 0, 1, 2 }; int N, M; int result = 1; cin ..

개요 https://www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 실버4 난이도 문제다. 풀이 처음 문제를 봤을 때는 그래프의 탐색으로 접근하려고 했다. 근데 그렇다고 하기엔 난이도가 낮았다. (꼼수 , , ) 처음에는 비행기를 탑승한 횟수인 줄 알았는데, 다시 보니 탑승한 비행기의 종류를 구하는 문제였다. 어차피 N개의 노드를 방문하려면 무조건 N-1개의 간선을 지나야 한다. 그래서 N-1을 출력해 줬더니 해결됐다. ..

개요 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 골드3 난이도 문제! 풀이 학생들이 파티가 열리는 마을에 갔다가 자신의 마을로 돌아와야한다. 이러한 학생들중 가장 오래 걸리는 학생의 소요시간을 출력하면 된다. 우선순위 큐를 이용한 다익스트라를 사용했다.(O(ElogE)) Dijkstra 함수의 매개변수로 출발지와 목적지를 받았다. 목적지에 도착했을 경우, 파티 장소인지 체크 후 파티장소일 경우 집을 목적지로 ..