어흥

문제 링크: www.acmicpc.net/problem/1253 1253번: 좋다 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) www.acmicpc.net 1. 주의할 점 - 원하는 숫자가 idx번째에 있다면, 서로 다른 두 수는 idx를 사용하여 만들어지면 안된다. 문제 설명이 모호하게 되어있다 3 0 0 3 -> 답: 0 2. 구현 - 투 포인터를 이용하여 풀이한다 - 입력 받은 수들을 오름차순으로 정렬하여 투포인터의 필요조건을 만족시킨다 - 0~N-1까지 모든 수에 대해 이분탐색을 수행한다 - Left는 0, Right는 N-1부터 수행한다 - 두 수가 같으면 안되므로 Le..

문제 링크: www.acmicpc.net/problem/20366 20366번: 같이 눈사람 만들래? 높이가 (2, 5), (3, 5)로 구성된 눈사람 둘을 만드는 것이 최적의 경우 중 하나이다. |7-8| = 1 다른 경우로는 (2, 9), (5, 5)로 두 눈사람을 만드는 경우가 있다. |11-10| = 1 www.acmicpc.net 1. 주의할 점 - 4개의 수를 어떤 방식으로 뽑을 것인지 잘 생각한다 - 정렬 이후, 인접합 4개를 조작하여 답을 구할 경우, 반례가 존재한다. 반례) 6 1 2 1000 2000 10001 10002 답: 0 2. 구현 - 조합을 통해 2개 공의 합이 나타낼 수 있는 높이를 벡터에 저장한다. 이때, 벡터는 사용한 번호 2개, 2개의 합 총 변수가 3개인 구조체 형태..

문제 링크: www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 1. 주의할 점 - 시간제한이 엄격하여 substr로 하면 TLE 발생한다 - 커서를 기준으로 앞의 문장과 뒤의 문장을 따로 저장한다 2. 구현 - 커서를 기준으로 앞의 문장은 Deque에, 뒤는 Stack에 저장한다 - 초기에 커서는 입력받은 문자의 맨 뒤에 위치하므로 Deque에 문자열을 전부 넣는다 - 명령어가 L이 들어왔다면, 왼쪽으로 커서를 움직여야하므로 덱이 비어있지 않다면 맨 뒤의 원소 ..

문제링크: www.acmicpc.net/problem/10799 10799번: 쇠막대기 여러 개의 쇠막대기를 레이저로 절단하려고 한다. 효율적인 작업을 위해서 쇠막대기를 아래에서 위로 겹쳐 놓고, 레이저를 위에서 수직으로 발사하여 쇠막대기들을 자른다. 쇠막대기와 레이저 www.acmicpc.net 1. 주의할 점 - 레이저가 쏘아질 때, 얼만큼 값이 추가되는지 확인한다 - 끝처리를 어떻게 할지 생각한다 2. 구현 - 레이저는 항상 () 형태로 입력되므로 '('다음에 ')'가 있으면 레이저, 없으면 쇠막대기의 연장선이라고 생각한다 - 쇠막대기면 Stack에 '('를 추가한다 - 레이저라면 Stack의 크기만큼 Result에 더한다(레이저를 기준으로 왼쪽 부분 추가) - 쇠막대기가 끝났다면, Result++..

문제 링크: www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 1. 주의할 점 - DFS, BFS, MST, 한줄 모두 가능 - 허무주의 2. 구현 [BFS] - 시작점을 1로 잡고(아무점이나 상관없다) Queue에 넣고 BFS를 수행한다. 방문하지 않은 Node가 있으면 Result++하고 Queue에 넣는다 #include #include #include using namespace std; vector v[1001];..

문제 링크: www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 1.주의할 점 - 메모리의 제한이 극단적이니 배열의 크기를 최소로 한다 2. 구현 - 각 줄을 Arr[]배열에 입력받는다 - 만약 첫 번째 줄이라면, Maxi[1][], Mini[1][] 배열에 그대로 값을 대입한다. Maxi[0][] 배열은 t번째 숫자를 입력받기전인 t-1번까지의 최대 점수를 저장하는 배열이다. Maxi[1][] 배열은 t번째 숫자를 받은 후, t번째까지의 최대 점수를 저장하는 배열이다. Mi..

문제 링크: www.acmicpc.net/problem/20422 20422번: 퀼린드롬 (Easy) 7과 r이 완전히 거울 대칭으로 보이지는 않지만, 상민이는 이 정도로 비슷하면 인정하기 때문에 거울 대칭 표에 7과 r은 거울 대칭이라고 적었다. www.acmicpc.net 1. 주의할 점 - 대칭되는 문자들을 미리 Map에 저장한다 - 하나하나씩 조건들을 만족하면서 풀어나간다 - 문자열의 길이가 홀수일 경우, 가장 중간에 위치한 문자열은 자기자신이 대칭이여야 한다 2. 구현 - make_map() 함수를 통해 대칭되는 문자들을 미리 Map에 저장한다 - (문자열의 길이+1)/2만큼 문자들을 비교한다 -> 위의 파란색 조건을 비교하기 위해 - 양끝에서부터 안쪽으로 차례대로 문자들을 비교한다 - 왼쪽에서..

문제 링크: www.acmicpc.net/problem/20419 20419번: 화살표 미로 (Easy) 첫번째 줄에는 미로의 행 R, 열 C, 준서가 가진 주문서 세트의 개수 K가 주어진다. 두번째 줄부터 R줄에 걸쳐 화살표 미로의 지도가 입력된다. 각 줄마다 "UDLR"로만 이루어진 길이 C의 문자열이 입 www.acmicpc.net 1. 주의할 점 - 주문서는 최대 1개 가질 수 있다 - 주문서는 왼쪽, 오른쪽 회전 1개가 세트다 2. 구현 - 미로를 입력받으면서 Check[][] 배열을 3으로 초기화시킨다. Check[][] 배열은 해당 지점에 몇개의 주문서를 사용해서 도착했는가?에 대한 정보를 담고있다 -> 시간절약위해 사용 - DFS()를 수행하며, 변수로는 Y, X, 사용한 오른쪽회전 주문서..