https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 문제 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 예제 입력 1 복사 2 예제 출력 1 복사 3 힌트 아래 그림은 3×12 벽을 타일로 채운 예시이다.... www.acmicpc.net d[i][j] = 3*i를 채우는 방법의 수, i열의 상태는 j 상태 다이나믹을 이용해서 경우의 수들을 구할 수 있다. 그림을 그려보면 쉽게 이해할 수 있다. i열을 계산할 때 i-1열은 꽉 차 있어야 한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 ..
https://www.acmicpc.net/problem/1328 1328번: 고층 빌딩 상근이가 살고있는 동네에는 빌딩 N개가 한 줄로 세워져 있다. 모든 빌딩의 높이는 1보다 크거나 같고, N보다 작거나 같으며, 같은 높이를 가지는 빌딩은 없다. 상근이는 학교 가는 길에 가장 왼쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았고, 집에 돌아오는 길에는 가장 오른쪽에 서서 빌딩을 몇 개 볼 수 있는지 보았다. 상근이는 가장 왼쪽과 오른쪽에서만 빌딩을 봤기 때문에, 빌딩이 어떤 순서로 위치해있는지는 알 수가 없다. 빌딩의 개수 N과 가장 왼쪽에서 www.acmicpc.net D[N][L][R] = 각각 1~N의 높이를 가진 빌딩을 세웠을 때 가장 왼쪽에서 L개, 가장 오른쪽에서 R개의 빌딩이 보이는 경우의 수..
https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net d[i][j] = 구간 [i,j]가 팰린드롬인지 여부 팰린드롬의 성질을 이용해서 구간을 확장시켜가면서 a[i]와 a[j]가 같을 때, d[i+1][j-1]이 참인지 확인하면 된다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 #include int i,j,k,n,m,p,q,a[2001]; bool d[2001][2001]; int main() { scanf("%d",&n); for(i=1;i
https://www.acmicpc.net/problem/1890 1890번: 점프 문제 N×N 게임판에 수가 적혀져 있다. 이 게임의 목표는 가장 왼쪽 위 칸에서 가장 오른쪽 아래 칸으로 규칙에 맞게 점프를 해서 가는 것이다. 각 칸에 적혀있는 수는 현재 칸에서 갈 수 있는 거리를 의미한다. 반드시 오른쪽이나 아래쪽으로만 이동해야 한다. 0은 더 이상 진행을 막는 종착점이며, 항상 현재 칸에 적혀있는 수만큼 오른쪽이나 아래로 가야 한다. 한 번 점프를 할 때, 방향을 바꾸면 안 된다. 즉, 한 칸에서 오른쪽으로 점프를 하거나, 아래로 www.acmicpc.net 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 #include typedef..
https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈 수 있다. 또, 미로 밖으 www.acmicpc.net d[i][j] = (1,1)에서 (i,j)까지 이동했을 때 얻을 수 있는 사탕의 개수의 최대값 d[i][j] = a[i][j]+max..
https://www.acmicpc.net/problem/9536 9536번: 여우는 어떻게 울지? 문제 고대 미스테리로 전해지는 여우의 울음소리를 밝혀내기 위해 한신이는 고성능 녹음기로 무장하고 숲으로 들어갔다. 하지만 숲에는 동물들이 가득해, 녹음된 음성에는 다른 동물들의 울음소리가 섞여 있다. 그러나 한신이는 철저한 준비를 해 왔기 때문에 다른 동물들이 어떤 울음소리를 내는지 정확히 알고 있다. 그러므로 그 소리를 모두 걸러내면 남은 잡음은 분명히 여우의 울음소리일 것이다. 입력 첫 번째 줄에는 테스트케이스의 개수 T가 입력된다. 각 테스트케이스는 www.acmicpc.net 123456789101112131415161718192021222324252627282930313233343536373839..
https://www.acmicpc.net/problem/1620 숫자 -> 포켓몬 이름: 미리 저장해둔 문자열 순서로 찾는다.포켓몬 이름 -> 숫자: 해시 테이블을 이용한다. 체이닝 방식을 사용했다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112#include #define MAX_DATA 25#define MAX_TABLE 100007#defi..
https://www.acmicpc.net/problem/1707 DFS로 노드를 탐색해가면서 마킹표시를 해준다. 이전 노드와 색이 같으면 이분그래프가 아니라고 판정한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include #define V 20050#define E 200050 struct NODE{ int node; struct NODE *next;}; NODE HEAD[V],POOL[E*2];int t,n,m,u,v,cnt,ans,visit[V]; void init(int n){ cnt=0; ans=1; f..
https://www.acmicpc.net/problem/2606 메모리풀로 그래프를 만들고 1번에 연결된 컴퓨터의 개수를 세준다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #define N 100 struct NODE{ int node; struct NODE *next;}; NODE HEAD[N+1],POOL[N*N];int n,m,u,v,cnt,ans,visit[N+1]; void make(int u,int v){ NODE *node=&POOL[cnt++]; node->node=v; node->next=HEAD[u].next; HEAD[u].next=node..