코드 낙서장

16719번: ZOAC 2018년 12월, 처음 시작하게 된 ZOAC의 오프닝을 맡은 성우는 누구보다 화려하게 ZOAC를 알리려 한다. 앞 글자부터 하나씩 보여주는 방식은 너무 식상하다고 생각한 성우는 문자열을 보여주는 새로 www.acmicpc.net 문제 확인 스택 혹은 dfs로 풀어도 되지만 간단한 로직으로 풀 수 있습니다. 풀이 문자열에서 사전 순으로 빠른 문자는 아스키 값으로 낮은 문자이므로 간단하게 대소 비교를 통해 구별할 수 있습니다. 문자열을 구간으로 나누고 해당 구간에서 가장 낮은 문자를 택해 해당 문자를 추가하고 이로 인하여 나뉘는 2개의 구간을 같은 방식으로 처리합니다. 백준 예시 STARTLINK 보면 0 ~ (N-1) 구간에서 가장 빠른 문자는 A입니다. 이로 인하여 ST / RT..

www.acmicpc.net/problem/9660 9660번: 돌 게임 6 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000) www.acmicpc.net 문제 확인 게임트리 문제입니다. 풀이 가지고 갈 수 있는 돌의 개수는 1, 3, 4개 이므로 현재 플레이어가 이길 수 있는 경우의 수는 현재 남은 돌에서 x 개를 가져가서 1, 3, 4를 만들 수 없는 수의 돌을 남기는 것입니다. 따라서 2, 7, 9, 14 .. 가 되며 이는 7로 나눈 나머지가 2, 0 인 경우입니다. 코드 1 2 3 4 5 6 7 8 9 10 #include int main() { long long n; scanf("%lld", &n); if (n % 7 == 0 || n % 7 == 2) printf(..

2493번: 탑 첫째 줄에 탑의 수를 나타내는 정수 N이 주어진다. N은 1 이상 500,000 이하이다. 둘째 줄에는 N개의 탑들의 높이가 직선상에 놓인 순서대로 하나의 빈칸을 사이에 두고 주어진다. 탑들의 높이는 1 www.acmicpc.net 문제 확인 배열 인덱스를 따라가면서 만족하는 인덱스를 찾는 방식으로 풀 수 있습니다. 스택을 활용하여 문제를 풀어도 비슷한 결과가 나옵니다. 풀이 2가지 경우로 나눕니다. 전에 입력받은 탑의 크기가 현재 탑 보다 큰 경우 : 현재 탑이 발사한 레이저 신호를 수신한 탑은 i - 1이 됩니다. 현재 탑이 작은 경우 : i - 1부터 수신 가능한 탑을 찾아 내려갑니다. i - 1 번째 탑이 발사한 레이저 신호를 어느 탑이 수신하였는가(dist[i-1])를 보고 수신..

1662번: 압축 압축되지 않은 문자열 S가 주어졌을 때, 이 문자열중 어떤 부분 문자열은 K(Q)와 같이 압축 할 수 있다. K는 한자리 정수이고, Q는 0자리 이상의 문자열이다. 이 Q라는 문자열이 K번 반복된다는 뜻이 www.acmicpc.net 문제 확인 괄호를 기준으로 이전 길이 값이 변경되므로 스택을 활용해서 풀 수 있습니다. 풀이 배열을 따라가면서 문자마다 3가지 경우로 나눌 수 있습니다. '(' : 바로 이전의 숫자의 곱만큼 길이가 길어지므로 ary[i-1], 이전 문자열의 길이를 저장합니다. ')' : 기록해둔 스텍을 반영합니다. 문자 : 현재 길이를 +1 합니다. 스택을 재활용하기 때문에 ')' 문자를 만나면 결과를 반영한 후 stack[top]=0 으로 초기화를 해 주어야 합니다. 코..

1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 확인 1000 x 1000 크기 이므로 완전 탐색으로 풀면 시간 초과가 나므로 dp로 풀어야 합니다. 풀이 dp 배열의 의미를 현재 위치에서 만들 수 있는 최대 크기의 정사각형으로 둡니다. 현재 위치(i, j)에서 만들 수 있는 가장 큰 정사각형은 (i-1, j), (i-1, j-1), (i, j-1)의 최솟값 + 1 이 됩니다. 그 이유는 (i-1, j-1)의 값이 뒷부분 정사각형을 채워주고 (i, j-1), (i-1, j) 값이 새로워 가로를 채워주는 역할을 하기 때문입니다. 다음의 경우 dp[i-1, j-1] = 3, d..

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 값은 되돌아가는 것을 방..