FandPROG FandPROG

-피보나치 수의 확장(1788, 백준) 간단한 DP문제였다. 피보나치수를 음수까지 확장시켜 계산하는 문제였는데, 간단히 문제에 나와있는데로 구현하면 맞는다. >점화식 0) { P_fibo[0] = 0; P_fibo[1] = 1; for (i = 2; i

-벽 부수고 이동하기 3(16933, 백준) 벽부수고이동하기와 같은 로직을 사용한다. dis[i][j][k][t] = 좌표 (i, j) 까지 k번 벽을부수며 갈때 t(밤, 낮구분)시간까지 흐른 시간으로 나타내며, BFS로 그래프 전체를 탐색하며 답을 찾을 수 있다. 더보기 #include #include #include using namespace std; int n, m, k; int map[1010][1010]; int dis[1010][1010][15][5]; int dx[5] = { 0, 0, 1, -1 }; int dy[5] = { 1, -1, 0, 0 }; struct dat { int x, y, br, time; }; void BFS(int x, int y) { int i, j; queue ..

-분수의 합(1735, 백준) 두 분수를 입력받아 두 분수의 합을 기약분수의 형태로 나타내는 문제이다. 우선, 두분수를 통분시킨후, 만들어진 분수의 분자, 분모를 가지고 GCD를 돌리면 되는 간단한 문제이다.(기약분수 -> 서로소 = GCD 가 1인경우) 더보기 #include int a, b; int c, d; int GCD(int x, int y) { if (y == 0) return x; else return GCD(y, x % y); } int main() { int i, j; scanf("%d %d", &a, &b); scanf("%d %d", &c, &d); int x = (a * d) + (c * b); int y = d * b; while (1) { int gc; if (x > y) gc ..

-자리배정(10157, 백준) N범위가 1000임으로 그냥 구현하면 된다. 정말 힘든 구현문제라고 생각한다. x, y변수를 잡아주어, x, y를 증가, 감소시켜가며 사각형을 채운뒤 k번째 좌표값을 출력하였다. 자꾸 이상한데 수가 덮어져서 한참 디버깅했다. 미리 조건들을 써놓고 코딩하면 좋을듯 하다. 더보기 #include int map[1010][1010]; int main() { int i, j; int C, R, K; scanf("%d %d %d", &C, &R, &K); int cnt = 1; int x = 1, y = 1; int now_cnt = 0, now_dis = 1, dis = 1; if (C * R < K) { printf("0"); return 0; } while (1) { if (K..

-로프(2217, Baekjoon) 간단한 그리디 문제였다. n개의 로프를 사용하여 가장 높은 무게를 들려면, 자신보다 들 수 있는 중량이 큰 로프의 수 곱하기 자신이 들 수 있는 중량의 크기가 가장 큰 로프를 고르면된다. 정렬을 이용하여 간단히 풀었다. 더보기 #include #include #include using namespace std; int n; vector vec; int main() { int i, ans = -2e9; scanf("%d", &n); for(i=0;i

-동물원(12907, Baekjoon) 규칙을 찾아 조건에 맞게 구현하는 간단한 문제였다. 동물의 종류는 토끼와 고양이밖에 없음으로, 똑같은 숫자가 2개를 넘어선 안되며, 0부터 연속하여 1씩증가하는 수로만 이루어져 있어야한다.(0, 1, 2, 3, 5같은 경우는 중간에 4가 빠져서, 안됨) 나는 입력받은 수들중 가장 큰 수를 mx변수에 담았다. 0부터 mx까지 반복하며, 한번도 나오지않은 수가있다면, 0 출력, 그전수보다 현재수가 더 많이(0, 1, 1 같이 0이 1번, 1이 2번나와 자신보다 1작은수의 개수보다 자신의 개수가 많은 경우는 불가능하다)나왔다면, 0을 출력하였다. 모두 처리 후, 남은 수들로 만들 수 있는 조합을 구하였다. 더보기 #include #include int n; int cnt..

-효율적인 해킹(1325, Baekjoon) 한번의 해킹으로 최대한 많은 컴퓨터를 해킹해야 함으로, 한 컴퓨터에서 BFS탐색을 하여, 몇개의 컴퓨터를 해킹 할 수 있는 지를 알아보는 단방향 그래프탐색 문제였다. 처음에 N범위가 10^4라서, 완전 탐색을 하면, O(n^2)이 걸려 시간초과가 아닐까 싶었지만 문제의 시간제한이 5초로 넉넉하기 때문에 괜찮았다. 더보기 #include #include #include using namespace std; int n, m; vector vec[10010]; int ch[10010], cnt[10010]; void BFS(int x) { int i, j; queue q; q.push(x); ch[x] = 1; while (!q.empty()) { int now =..

문제 : https://www.acmicpc.net/problem/1074무엇을 구하는 문제인가?n이 주어졌을 때, 2^n * 2^n의 정사각형에서 4등분 후 문제에서 주어진 순서대로 탐색할 때, (r, c)는 몇번째로 나오는지 구하는 문제이다.​해결 전략4등분으로 분할하여, 문제에서 주어진 순서대로 호출하면 되는 간단한 문제이다.4등분하여, r, c가 포함될 때만 호출하여 주었다.​알고리즘1. n, r, c를 입력받는다.2. Divde(초기 x, 초기 y, 길이)를 (0, 0, 2^n)을 초기값으로 함수를 호출하여준다.3. 함수내에서 4등분 후 문제의 조건대로 차례로 호출하여준다.4. x좌표, y좌표가 같다면 ans에 지금의 번지수를 넣어준다.5. ans 출력​※주의 할점전체탐색을 해서는 안된다.  r..