나쿠리 개발 메모장

개요 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 함수의 매개변수로 출발지와 목적지를 받았다. 목적지에 도착했을 경우, 파티 장소인지 체크 후 파티장소일 경우 집을 목적지로 ..

개요 https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 골드5 난이도 문제다. 풀이 가중치 그래프 문제로 기본적인 다익스트라 알고리즘 문제 유형이다. V> N >> M; for (int i = 0; i > a >> b >> c; graph[a].push_back({ b, c }); graph[b].push_back({ a, c }); } Dijkstra(); cout

개요 https://www.acmicpc.net/problem/1043 1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 골드4 난이도 문제다. 풀이 유니온 파인드로 해결할 수 있다. 진실을 아는 사람의 parent를 -1로 초기화하고, 이를 루트 노드로 사용했다. 파티에 2명이상 있는 경우 Union 연산으로 합쳐주었다. 진실을 아는 사람과 같은 파티에 참석한 사람은 모두 진실을 아는 사람이 된다. (해당 파티에서 진실을 듣기 때문) 때문에 파티들의 첫 번째 손님의 루트 노드를 Find하며 거짓말 할 수 있는 파티인지 ..