코드 낙서장

1126번: 같은 탑 첫째 줄에 조각의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에 각 조각의 높이가 주어진다. 높이는 500,000보다 작거나 같은 자연수이고, 모든 조각의 높이의 합은 500,000을 넘 www.acmicpc.net 문제 확인 dp 문제입니다. left, right를 나누어 dp를 작성하면 dp[500000][500000]이 되므로 메모리 초과가 일어나기 때문에 | left-right | 를 기준으로 dp를 작성해야 합니다. 풀이 탐색 횟수를 줄이기 위해 입력 받은 수를 정렬하고 현재 단계에서 갈 수 있는 최댓값까지 탐색을 합니다. 조각을 쌓을 때 2가지 경우로 나눌 수 있습니다. 높은 탑에 쌓기 : 높은 탑에 쌓는 경우 현재 dp[j] 를 가리키고 있으며 ..

20541번: 앨범정리 지혜는 컴퓨터에 있는 사진들을 정리하기 위해 앨범정리 프로그램을 만들었다. 지혜가 만든 앨범정리 프로그램은 기본적으로 "album" 앨범이 존재하며 "album" 앨범은 절대로 삭제할 수 없다. www.acmicpc.net 문제 확인 알고리즘이 필요 없는 구현 문제입니다. 풀이 주어진 문제대로 구현을 하면 간단하게 풀 수 있습니다. 앨범, 사진 모두 중복이 허용되지 않으므로 앨범은 map, 사진은 set 컨테이너를 활용해서 관리합니다. 주의해야 할 것은 rmalb을 구현할 때 앨범을 삭제하면 하위 앨범 모두 삭제가 되어 삭제한 앨범수 = 1 + 삭제할 앨범의 모든 하위 앨범, 삭제한 사진 수 = 하위 앨범들의 사진 수 가 됩니다. 이를 위해 트리 탐색을 하면 많은 시간이 걸리므로 ..

16225번: 제271회 웰노운컵 첫 줄에 짝수 N(2 ≤ N ≤ 200,000)이 주어진다. 다음 줄에 A[1], ..., A[N], 그 다음 줄에 B[1], ..., B[N]이 (1 ≤ A[i], B[i] ≤ 109) 주어진다. 모든 A[i]는 서로 다르고, 모든 B[i]도 서로 다르다. www.acmicpc.net 문제 확인 정렬과 그리디 문제입니다. 풀이 B 기준으로 정렬하고 나면 왼쪽 수와 오른쪽 수를 묶어서 왼쪽 수 들의 합을 최대화하는 문제가 됩니다. B를 기준으로 정렬을 하고 나면 2 수를 묶어 왼쪽 수를 선택하게 되므로 0번째 수는 항상 선택이 되며 n-1 번째 수는 항상 고를 수 없게 됩니다. 위와 같은 경우 답은 7, 6, 5 => 18이 됩니다. 두 수를 쌍으로 묶으며 선택하는 방법..

2879번: 코딩은 예쁘게 첫째 줄에 줄의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 현재 줄에 있는 탭의 개수가 주어지며, 1번째 줄부터 순서대로 주어진다. 탭의 개수는 0보다 크거나 같고, 80보다 작거나 같은 정수 www.acmicpc.net 문제 확인 특별한 알고리즘이 필요 없는 구현 문제입니다. 풀이 먼저 값을 쉽게 비교하기 위해서 "현재 탭의 수 - 올바른 탭의 개수"로 배열에 저장합니다. 4 1 2 3 4 3 1 1 0 위와 같은 경우 배열에는 -2 1 2 4 로 저장 될 것입니다. 문제에서 주어진 조건에 따라 연속된 줄을 한번에 편집이 가능하며 주의해야 할 점은 편집할 때 추가, 삭제 중 한가지만 가능하다는 것입니다. 따라서 -2, 1 를 그룹으로 선택하여 편집하는 것 보..

1016번: 제곱 ㄴㄴ 수 어떤 수 X가 1보다 큰 제곱수로 나누어 떨어지지 않을 때, 제곱ㄴㄴ수라고 한다. 제곱수는 정수의 제곱이다. min과 max가 주어지면, min과 max를 포함한 사이에 제곱ㄴㄴ수가 몇 개 있는지 출력한다. www.acmicpc.net 문제 확인 수학을 사용해서 푸는 문제입니다. 풀이 bool 배열은 char와 마찬가지로 1byte를 사용하기 때문에 메모리 사용량이 적은 bitset 객체를 사용합니다. 조건에 따라 모든 수의 비트를 만들순 없기 때문에 min ~ max 간격의 최댓값인 1000001개의 비트를 만듭니다. min ~ max 사이에 있는 수에 각각 비트를 할당하고 각 수는 index - a 위치에 저장됩니다. 초기값은 false, 0입니다. 제곱수 4, 9, 16,..

2560번: 짚신벌레 첫째 줄에 a, b, d, N을 나타내는 네 정수가 빈칸 하나를 사이에 두고 차례로 주어진다. 단, 0＜a＜b＜d≤10,000이고, 1≤N≤1,000,000이다. www.acmicpc.net 문제 확인 원형 큐 자료구조 형식을 응용하는 문제입니다. 모든 짚신벌레를 관리하면 메모리 초과가 일어나며 a, b, d를 고정시키고 배열을 움직이게 되면 연산이 많아져 시간 초과가 납니다. 따라서 배열의 값 대신 a, b, d를 인덱스로 이용하여 풀어야 합니다. 풀이 문제에서 주어진 d 값을 이용해 원형 큐 배열을 만듭니다. d는 최대 10000이며 이를 넘을 시 짚신벌레는 죽기 때문에 배열을 ary[10001]로 선언합니다. 초기 배열을 [1, 0, 0, ...] 으로 초기화해주고 a, b, ..

15681번: 트리와 쿼리 트리의 정점의 수 N과 루트의 번호 R, 쿼리의 수 Q가 주어진다. (2 ≤ N ≤ 105, 1 ≤ R ≤ N, 1 ≤ Q ≤ 105) 이어 N-1줄에 걸쳐, U V의 형태로 트리에 속한 간선의 정보가 주어진다. (1 ≤ U, V ≤ N, U ≠ V) www.acmicpc.net 문제 확인 트리 dp 문제입니다. 풀이 그래프를 입력받아서 작성하고 dfs를 통해 dp 값을 채워 넣어주면 됩니다. 자신을 포함하여 서브트리의 정점 개수이므로 초기값은 1로 설정을 하고 자식들의 dp값을 합쳐주면 결과를 얻어낼 수 있습니다. for(auto child : cur.edge) if(child != prev) dp[cur] += dfs(child, cur); prev 값은 되돌아가는 것을 방..

1422번: 숫자의 신 첫째 줄에 K와 N이 공백을 사이에 두고 주어진다. K와 N은 각각 1,000보다 작거나 같은 자연수이고, N은 K보다 크거나 같다. 둘째 줄에는 K개의 수가 한 줄에 하나씩 주어진다. 각 수는 1,000,000,000보 www.acmicpc.net 문제 확인 문자열 혹은 숫자 자릿수를 활용하는 문제입니다. 풀이 간략한 풀이를 위해 입력을 문자열로 받습니다. 최대의 숫자를 만들기 위해서는 몇 가지를 고려해야 합니다. 맨 앞자리는 1~9 중 재일 높은 수가 나와야 합니다. 모든 수를 고르고 난 후 남은 n-k개의 수는 가장 긴 자릿수 중 재일 높은 수를 선택해야 합니다. 1번을 고려할때 주의해야 할 점은 91, 9 의 경우9/91이 더 높은 숫자를 만들 수 있는 것입니다. 이를 위해..

문제 주소 : www.acmicpc.net/problem/14725 14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N개가 주어진다. (1 ≤ N ≤ 1000) 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 www.acmicpc.net 문제 확인 문자열과 정렬을 이용해서 풀 수 있습니다. 풀이 입력받을 시 문자열 다음에는 공백 혹은 \0이 입력되고 이를 구분해서 풀 수 있습니다. fgets를 통해 한번에 문자열 집합을 입력받고 qsort 함수를 통해 정렬을 합니다. qsort 정렬 시 strcmp 함수를 통해 같은 굴에서 뻣어가는 굴일 경우 교차점 이전까지 문자가 모두 같기 때문에 사전 순서대로 정렬됨을 이용합니다..

문제 주소 : www.acmicpc.net/problem/2983 2983번: 개구리 공주 트럭을 타고 이동하던 중에 상근이는 휴식을 취하기 위해서 호수에 잠시 들렸다. 호수에는 개구리가 살고 있고, 개구리는 호수 위에 떠있는 식물 N개를 점프하면서 다닌다. 오래된 전설에 따르 www.acmicpc.net 문제 확인 링크로 연결해서 풀 수 있지만 링크를 사용하는 것 자체가 인덱싱에 비하여 느리므로 그래프 형식으로 인덱스를 저장해서 풀었습니다. 풀이 개구리는 4방향 (P, P), (-P, -P), (-P, P), (P, -P) 방향으로 점프를 하기 때문에 x, y축에 대하여 식을 새워 다음과 같이 m값으로 나타냅니다. 따라서 점 x, y에서 특정 방향으로 이동하기 위해서는 x, y와 움직일 위치가 같은 m..