어흥

문제 링크: www.acmicpc.net/problem/1484 1484번: 다이어트 첫째 줄부터 한 줄에 하나씩 가능한 성원이의 현재 몸무게를 오름차순으로 출력한다. 가능한 몸무게가 없을 때는 -1을 출력한다. 현재 몸무게는 자연수로 떨어지지 않을 수도 있는데, 이런 경우 www.acmicpc.net 1. 주의할 점 - a*a - b*b = (a+b)*(a-b)로 접근한다 2. 구현 - G = (a+b)*(a-b)라고 생각하여 G의 약수중에서 작은 값을 V벡터에 넣는다. 즉, a-b의 값을 V에 너흔ㄴ다 - V에 있는 값을 통해 a+b를 구한다. - {(a+b) + (a-b)}/2 = a 식을 통해 a를 구한다. 이때, 좌변은 2로 나누기 전, 짝수여야 한다 - 모든 a 값을 ans벡터에 넣고 정렬한 ..

문제 링크: www.acmicpc.net/problem/2458 2458번: 키 순서 1번부터 N번까지 번호가 붙여져 있는 학생들에 대하여 두 학생끼리 키를 비교한 결과의 일부가 주어져 있다. 단, N명의 학생들의 키는 모두 다르다고 가정한다. 예를 들어, 6명의 학생들에 대하여 www.acmicpc.net 1. 주의할 점 - 한 학생이 자신의 순서를 정확히 아는 경우: 앞에서 몇번째인지 + 뒤에서 몇번째인지 2. 구현 - 모든 순서에 대한 정보를 V[] 벡터에 담는다. 이때, 앞에 나온 수 V[A]에 뒤에 나온 수 B를 추가한다 - 모든 학생들에 대해서 단방향 BFS를 수행하며 해당 학생이 몇명의 다른 학생에게 도달이 가능한지(자기보다 큰 사람)를 canReach[]++를 통해 저장하며, 도달당한 학생..

문제 링크: www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 첫째 줄에 테스트 케이스의 개수 T(1

문제 링크: 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.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[][] 배열에 ..