https://www.acmicpc.net/problem/14428🔥바로 아래 코드는 틀린 코드🔥문제를 처음 읽고 별 생각없이 바로 코드를 작성하면 아래와 같이 코드를 작성할 것이다.하지만 주석에도 써놨듯이 아래 코드로 작성하면 시간초과를 받게 될 것이다.#include using namespace std;#define endl '\n'#define SIZE 100001int N, T;int arr[SIZE];void initInput() { cin >> N; for (int i = 1; i > arr[i]; cin >> T;}void solve() { int type, i, j; // O(TN + T) -> O(10,000,000,000) // 제한 시간 2초안에 해..

10476번: 좁은 미술전시관 기다랗고 2N개의 방이 있는 미술관이 있다. 미술관은 세로로 N줄, 가로로 2칸의 방으로 구성된다. 위아래, 양 옆으로 붙어있는 방들은 서로 연결되어 있다. 오늘의 큐레이터는 미술관 운영진으로 www.acmicpc.net #include #include using namespace std; #define endl '\n' #define INF 1e9 #define SIZE 201 int N, M, sum; int arr[SIZE][2]; int dp[SIZE][SIZE][3]; void initInput() { cin >> N >> M; for (int i = 1; i > arr[i][j]; sum += arr[i][j]; } } for (int i = 1; i

9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net BFS로 해결할 수 있는 문제다. 네 가지 연산(D, S, L, R)에 대한 함수를 만들어 놓고, 함수 포인터로 네 가지 함수를 순차적으로 호출한다. 함수들은 연산을 끝낸 뒤 함수의 이름을 반환해 큐에 삽입하기 위한 문자열을 만든다. 연산된 숫자와 문자열을 큐에 삽입한다. 동일한 숫자에 대한 중복 연산을 막기 위해 visited 배열을 사용한다. 숫자를 기준으로 visited 배열을 검사하며 중복 연산을 막는다. #include #include #i..

2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 타일 채우기 문제이므로 다이나맥 프로그래밍(DP)로 해결할 수 있다. 입력값이 홀수인 경우는 타일을 채울 수 없으므로 0이 된다. 따라서 입력값이 짝수인 경우만 고려하면 된다. DP로 해결하기 위해 타일을 채울 최소 단위를 구했다. 타일을 채울 수 있는 가장 작은 크기는 2이다. 이때 타일을 채울 수 있는 방법은 3가지이고, 이것을 최소단위로 사용해 문제를 해결할 것이다. DP 유도식을 점화식으로 만들었고 이를 바탕으로 코드화했다. #include using namespace std; #define endl '\n' #define SIZE 31 int N; int dp[S..

3584번: 가장 가까운 공통 조상 루트가 있는 트리(rooted tree)가 주어지고, 그 트리 상의 두 정점이 주어질 때 그들의 가장 가까운 공통 조상(Nearest Common Anscestor)은 다음과 같이 정의됩니다. 두 노드의 가장 가까운 공통 조상은, 두 www.acmicpc.net #include using namespace std; #define endl '\n' #define SIZE 10001 int T, N; int parent[SIZE]; bool visited[SIZE]; void initInput() { cin >> T; } void solve() { while (T--) { int u, v; cin >> N; for (int i = 1; i > u >> v; parent[v..

16565번: N포커 첫째 줄에 N장의 카드를 뽑았을 때, 플레이어가 이기는 경우의 수를 10,007로 나눈 나머지를 출력하라. www.acmicpc.net 이 문제를 처음 봤을 땐 그냥 "52 / N"을 출력하면 되는거 아닌가? 하는 생각을 했다. 근데 이 문제의 난이도가 골드2 이기 때문에 이런 쉬운 문제는 아닐 것 같아서 좀 더 고민해봤다. 생각의 결론은 이렇다. 이 문제는 경우의 수를 구하는 것이다. 경우의 수는 중복된 경우를 카운트하지 않기 때문에 이 경우를 제외해줘야 한다. 조합(combination) 계산을 위한 표는 미리 만들었다. (makeCombination() 함수) 나머지는 위 과정을 코드화 했다. #include using namespace std; #define endl '\n'..

14725번: 개미굴 첫 번째 줄은 로봇 개미가 각 층을 따라 내려오면서 알게 된 먹이의 정보 개수 N (1 ≤ N ≤ 1000)개가 주어진다. 두 번째 줄부터 N+1 번째 줄까지, 각 줄의 시작은 로봇 개미 한마리가 보내준 먹이 정 www.acmicpc.net '로봇 개미가 지나온 경로 자체를 문자열로 처리를 한 뒤 중복을 제거하면 되지 않을까' 라는 생각을 했다. 만약 입력 값이 "KIWI-APPLE-BANANA" 라고 한다면, 이 경로를 다음과 같이 처리하는 것이다. -KIWI -KIWI-APPLE -KIWI-APPLE-BANANA 이렇게 입력 받은 경로를 위 처럼 3개의 문자열로 저장하는 것이다. 중복을 제거하기 위해서 문자열을 저장할 때는 set을 사용했다. (정렬까지 해주니 더 좋다.) 이런 ..

2533번: 사회망 서비스(SNS) 페이스북, 트위터, 카카오톡과 같은 사회망 서비스(SNS)가 널리 사용됨에 따라, 사회망을 통하여 사람들이 어떻게 새로운 아이디어를 받아들이게 되는가를 이해하는 문제가 중요해졌다. 사회망 www.acmicpc.net #include #include #include using namespace std; #define endl '\n' #define SIZE 1000001 #define EARLY 0 #define NORMAL 1 int N; vector tree[SIZE]; int dp[SIZE][2]; bool visited[SIZE]; void initInput() { cin >> N; for (int i = 0; i < N - 1; i++) { int u, v; c..