어흥

문제 링크: www.acmicpc.net/problem/2143 2143번: 두 배열의 합 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다 www.acmicpc.net 1. 주의할 점 - 메모리 제한이 작다. 메모리를 최대한 적게 쓰도록 한다 - Map을 1개 사용하고, 이분탐색을 통해 답을 유추한다 2. 구현 - A배열과 B배열을 입력받은 후, A배열에서 만들 수 있는 부분 배열을 Ma Map에 저장한다(숫자, 해당 숫자를 만들 수 있는 개수) - B배열의 부분 배열을 구할 때마다 Ma..

문제 링크: www.acmicpc.net/problem/13422 13422번: 도둑 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 T가 주어진다. 각각의 테스트 케이스의 첫째 줄에 마� www.acmicpc.net 1. 주의할 점 - N과 M이 같을때의 조건을 잘 세운다 - 최대 몇개를 확인하면 되는지 식을 잘 세운다 - While문 안에 For문을 이용하여 Sum을 계산하지 않는다 -> 두 포인터를 활용한다 2. 구현 - 입력받을 배열의 크기를 2배로 하여 N + M -1개의 배열에서 연속된 M개씩 고르도록 한다 - While문을 몇번 반복할것인지 Len을 구해야 한다. Len : 기존배열에서 한바퀴 더 돌아서 ..

문제 링크: www.acmicpc.net/problem/14391 14391번: 종이 조각 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, www.acmicpc.net 1. 주의할 점 - 최대 4*4이므로, 브루트포스 알고리즘을 사용한다 - 사용한 숫자처리를 제대로 하면 된다 2. 구현 - 배열을 입력받은 후, 왼쪽위 원소부터 브루트포스를 수행한다 - 브루트포스는 다음과 같은 순서로 진행된다. 해당 원소만 포함, 해당 원소포함 + 아래숫자들 포함, 해당 원소포함 + 오른쪽 숫자들 포함 - 단, 위의 기준은 항상 추가할 숫자가 방문처리되어 있지 않다는 가정하에 진..

문제 링크: www.acmicpc.net/problem/16971 16971번: 배열 B의 값 첫째 줄에 배열 A의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 배열의 원소가 주어진다. 배열은 정수로만 이루어져 있다. www.acmicpc.net 1. 주의할 점 - 각각의 원소가 배열 B가 만들어지기 위해 몇번 사용되는지 미리 계산한다. 다음과 같다 N = 10, M = 6의 경우, 배열 A의 각 원소가 더해지는 횟수 //1~M열 1 2 2 2 2 1//1행 2 4 4 4 4 2 2 4 4 4 4 2 2 4 4 4 4 2 2 4 4 4 4 2 2 4 4 4 4 2 ~ 2 4 4 4 4 2 2 4 4 4 4 2 2 4 4 4 4 2 1 2 2 2 2 1//N행 즉, 맨 위와 아래행(K번)은 나머지 ..

문제 링크: www.acmicpc.net/problem/1904 1904번: 01타일 지원이에게 2진 수열을 가르쳐 주기 위해, 지원이 아버지는 그에게 타일들을 선물해주셨다. 그리고 이 각각의 타일들은 0 또는 1이 쓰여 있는 낱장의 타일들이다. 어느 날 짓궂은 동주가 지원이�� www.acmicpc.net 1. 주의할 점 - DP를 사용해서 문제를 해결한다(점화식) 2. 구현 - 1개의 타일: 1개(1) - 2개의 타일: 2개(00, 11) - N개의 타일을 사용할 때 : (N-1개의 타일 + N-2개의 타일)%MOD (여기서 MOD는 15746) 따라서 점화식은 N>=3일때, Arr[N] = (Arr[N-1] + Arr[N-2])%MOD로 이루어진다 #define MOD 15746 #include u..

문제 링크: https://www.acmicpc.net/problem/16562 16562번: 친구비 첫 줄에 학생 수 N (1 ≤ N ≤ 10,000)과 친구관계 수 M (0 ≤ M ≤ 10,000), 가지고 있는 돈 k (1 ≤ k ≤ 10,000,000)가 주어진다. 두번째 줄에 N개의 각각의 학생이 원하는 친구비 Ai가 주어진다. ( www.acmicpc.net 1. 주의할 점 - 분리집합으로 집단을 나눈 이후, 그 집단에서 가장 작은 친구비를 더한다 2. 구현 - 입력을 받으면서 Par[](자신의 조상을 나타냄)배열을 초기화한다 - 친구 관계를 입력받을 때, 같은 집합이 형성되도록 Make_union() 함수를 사용한다. 그리고 Make_union() 함수를 사용할 때, 작은 친구비를 가진 학생..

문제 링크: https://www.acmicpc.net/problem/1238 1238번: 파티 문제 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 www.acmicpc.net 1. 주의할 점 - 초기화를 잘 한다 - 다익스트라 알고리즘을 통해 최단거리를 구한다 - 파티로 가는, 그리고 나가는 거리의 최단거리를 구하기 위해 그래프의 방향이 반대인것도 구해서 벡터 V[][]에 저장한다 2. 구현 - 입력받은 단방향 그래프: 파티 -> 집으로 갈때의 최단거리 - 입력받은 단방향 그래프에서 방향을 반대로: 집 -> 파티까지의 최단거리 - 입력받을 때 단방향그..

문제 링크: https://www.acmicpc.net/problem/4889 4889번: 안정적인 문자열 문제 여는 괄호와 닫는 괄호만으로 이루어진 문자열이 주어진다. 여기서 안정적인 문자열을 만들기 위한 최소 연산의 수를 구하려고 한다. 안정적인 문자열의 정의란 다음과 같다. 빈 문자열은 www.acmicpc.net 1. 주의할 점 - 전부 한번씩 뒤집어서 비교하는 일은 하지 않도록 한다(최악: 2^2000) 2. 구현 - 초기에 문자열을 입력받을 때, Stack에 문자를 1개씩 넣는다. 단, {}와 같이 쌍을 이룰경우, Stack에서 제외한다 - 위의 과정을 통해 안정적이지 못한 문자열이 Stack에 있을때, 가장 위에 위치한 원소 2개씩 뺀다 (문자열의 길이가 짝수이므로 가능하다) - 원소 2개가..