어흥

문제 링크: www.acmicpc.net/problem/16437 16437번: 양 구출 작전 2, 3, 5번에 사는 모든 양들은 1번 섬으로 갈 수 있지만 7번 섬에 사는 양들은 1번 섬으로 가기 위하여 6번 섬을 거쳐야 하는데 6번 섬에 사는 늑대들의 수가 7번 섬에 사는 양들의 수보다 많으므로 www.acmicpc.net 1. 주의할 점 - 모든 섬에 양이 최대치로 존재 -> 합해지는 과정에서 Int의 범위를 벗어날 수 있다 2. 구현 - 위상정렬의 풀이법으로 접근했다 - Info 구조체를 통해 해당 지점을 도착지점으로 설정한 섬의 수(Conn), 다음 섬으로 연결된 곳(To), 생물의 수(Val)를 나타낸다 - 섬에 늑대가 존재하면, 생물의 개수를 음수로 저장한다. - Info의 성격에 맞게 Ar..

문제 링크: www.hackerrank.com/challenges/game-of-thrones/problem?utm_campaign=challenge-recommendation&utm_medium=email&utm_source=7-day-campaign Game of Thrones - I | HackerRank Check whether any anagram of a string can be a palindrome or not. www.hackerrank.com 1. 주의할 점 - 팰린드롬을 직접 만들려고 하지 않는다 2. 구현 - 파라미터로 넘겨받은 S에 포함된 문자들의 수를 Alpha[] 배열에 갱신한다 - Alpha[] 배열의 값이 홀수인 경우, 팰린드롬을 생성할 때 무조건 가운데에 위치해야 하므로 ..

문제 링크: www.acmicpc.net/problem/2437 2437번: 저울 하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓 www.acmicpc.net 1) 주의할 점 - 브루트포스 -> 2^1000 -> TLE발생 - DP -> 방법이 떠오르지 않는다 2) 구현 - 도저히 방법이 떠오르지 않아 질문게시판에서 힌트를 얻어서 해결했다 - 우선 Result = 1로 설정을 한다(양의 정수 중 가장 낮은 값이므로). 이때, Result는 지금까지 원소들의 합 + 1이라고 생각하면 된다 - 입력받은 모든 수를 Arr[]배열에 저장한 후, 오름차순으로 정렬한다 - 0..

문제 링크: www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net 1. 주의할 점 - 동맹 처리를 어떻게 할 것인가? - 전쟁 처리를 어떻게 할 것인가? 빠트린 조건은 없는가 2. 구현 - 동맹 처리: 공통조상 설정 + 공통조상으로 병력합친다 - 전쟁 처리: 병력 감소 + 한 국가 멸망 + 속국 처리(이 부분을 까먹기 쉽다) - Par[] 배열을 통해 자신의 조상을 나타낸다 - Power[] 배열을 통해 한 나라..

문제 링크: www.acmicpc.net/problem/2922 2922번: 즐거운 단어 상근이는 자신이 다니는 학교에서 영어단어를 가장 많이 외우고 있다. 그 비법은 바로 조기교육이었다. 상근이는 젖병을 물기도 전에 영어 단어를 외웠다. 따라서, 지금은 자리에 앉으면 사전을 www.acmicpc.net 1. 주의할 점 - 정답은 Long Long 형태다 - 그리디한 방법으로 접근한다 - 모음↔L↔L이 아닌 자음 총 3가지의 경우를 두고 한다 2. 구현 - Dfs() 함수를 통해 시작하며, 매개변수로는 현재 index 번호, 연속된 모음의 수, 연속된 자음의 수, L의 여부, 현재까지의 형태로 진행될 수 있는 수가 차례대로 입력된다 - 입력받은 Str에 대해 모든 탐색이 끝났고, L이 있었다면 Resul..

문제 링크: www.acmicpc.net/problem/20061 20061번: 모노미노도미노 2 모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, www.acmicpc.net 1. 주의할 점 - 모든 절차에 따른 함수를 정확히 구현해야 한다 - 연한색에 위치함으로 인해 사라지는 열/행은 점수에 반영되지 않는다 2. 구현 - 입력에 대해 블록을 V 벡터에 구조체 형태로 저장한다 - MV(0) ->Pop_down() -> MV(1) -> Pop_right() 함수가 한 사이클이다 - MV(0)을 통해 V에 저장된 형태의 블록을 아래로 내려서 Arr[][] 배열에 ..

문제 링크: www.acmicpc.net/problem/1561 1561번: 놀이 공원 첫째 줄에 N(1 ≤ N ≤ 2,000,000,000)과 M(1 ≤ M ≤ 10,000)이 빈칸을 사이에 두고 주어진다. 둘째 줄에는 각 놀이기구의 운행 시간을 나타내는 M개의 자연수가 순서대로 주어진다. 운행 시간은 1 이상 30 www.acmicpc.net 1. 주의할 점 - N num>>play; for(int i=1;i>arr[i]; if(num

문제 링크: www.acmicpc.net/problem/3745 3745번: 오름세 입력은 여러개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 주가를 관찰한 날의 수 N (N ≤ 100000)이 주어진다. 둘째 줄에는 관찰한 주가가 첫 날부터 순서대로 주어진다. www.acmicpc.net 1. 주의할 점 - 이분탐색을 사용하는 LIS 알고리즘에 대해 알고 있어야 한다 - DP[] 배열을 TC마다 초기화한다 2. 구현 - 입력 받는 수들을 Arr[] 배열에 저장하면서 DP[] 배열을 전부 0으로 초기화한다 - DP[0] = Arr[0]과 idx=0을 초기화한다 - i: 1~Num-1까지 Arr[]에 있는 모든 수들에 대해 Arr[i]의 값이 DP[idx]보다 크다면 DP[++idx]..