KPU CE

문제 해결 일반적으로 사용하는 bfs 케이스(상하좌우)에 체스 말 케이스를 추가해서 12가지의 케이스를 고려해서 bfs 코드르 작성하렸다. 여기서 주위해야될 점은 체스말로 이동한 곳은 따로 visit를 해야된다. visit을 할때 그곳이 k가 0~30번까지 올 수 있기 때문이다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 #include #..

문제 https://www.codeground.org/practice 문제해결 문제를 보고 바로 시뮬레이션 문제라는 것을 직감했다. 방향만 잘 컨트롤 해준다면 문제없이 풀 수 있다. 더 효율적으로도 짤 수 있었겠지만 경우의 수가 별로 없어서 방햘 전환을 if문 만으로 해결하였다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 #include #include #include using namespace std; int map[1001][1001]; b..

문제 https://www.codeground.org/practice 문제해결 처음 고안한 방법으로는 다이나믹 프로그래밍으로 1~N까지 그때그때마다 최소로 점프할 수 있는 횟수를 업데이트해줘서 마지막 목적지까지 구해주는 방식으로 했으나 시간초과로 80점을 받았다... O(N)으로 풀어야 했기에 한번에 반복문만을 사용해야만 한다. 다음위치 > T; for(test_case = 0; test_case > N; for(int i = 1;i> bridge[i]; } cin >> K; int temp = 0; // 현재자리수+K를 저장 즉 최대로 건넜을때 위치임 int location = 0; //위치, 즉 최대로 건널 수 있는 돌다리의 위치를 저장한것(현재 와있는 위치라고 생각하면됨) int sol = 0; /..

문제 https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 알고리즘 풀이 1. 미세먼지를 분산시킬때는 동시에 일어나는 것이기 때문에 배열에 하나하나 접근해서 바꾸다 보면 분산시켜서 더해준 구역을 분산시켜서 동시에 한다는 조건을 만족하지 못한다. 그렇기 때문에 임시로 저장해놓을 배열을 하나 만들어서 분산시키는 것과 분산시킨 구역의 남은 미세먼지 값을 임시 배열에 저장한다. 2. 임시 배열의 값들을 진짜 배열에 복사해준다. 3. 공기청정기는 공기가 지..

문제 https://www.acmicpc.net/problem/15686 15686번: 치킨 배달 크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸 www.acmicpc.net 이 문제를 처음 봤을 때 그냥 간단한 브루트포스 문제인 줄 알고 풀었다가 시간초과가 계속 나와서 다른 블로그를 보고 서야 풀 수 있었다... 길이를 구하는 것을 처음에는 집,치킨집 좌표를 기억해서 구하는 식으로 했다가 시간초과가 나서 bfs로 했는데 런타임에러가 떠서 결국에는 블로그를 찾아서 풀었다. 알고리즘 설명 1. 집,치킨집의 좌표를 벡터에 저장한다. 2. visi..

문제 https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net 문제 해결 문제에서 주어진 점화식을 다이나믹으로 그대로 구현하였다. 코드 #include using namespace std; int main(void){ int N; long long dp[36],temp = 0; dp[0] = 1; dp[1]..

심심해서 평소에 만들고 싶었던 바둑판을 만들어 보려고 한다. 대국을 할 수 있는 바둑판이다. 1일차에서는 간단한 인터페이스와 흑,백이 둔 곳을 맵을 출력해서 보여지게 하는 작업과 2일차에 있을 돌을 따먹는 과정을 bfs로 어느정도 구현을 했다. 2일차에서는 돌을 따먹는 것을 구현한 후 인터페이스를 개선할 것이다. 계가 시스템과 패싸움 같은 부분을 구현 할 생각에 막막하지만 할 수 있을 거라 믿고 있다... 1일차 코드 #include #include #include using namespace std; /* map 설명 검은돌은 9, 흰색돌은 7, 맨바닥은 0 */ string map[20][20]; int b_catch = 0,w_catch = 0,cnt = 0; bool b = false,w = fa..

문제 https://www.acmicpc.net/group/board/view/9362/19864 로그인 www.acmicpc.net 문제해결 다이나믹 프로그래밍으로 풀었다. fibo(n) = fibo(n-1) +fibo(n-2) 이라는 식을 규칙을 보고 유추하여서 배열로 구현하였다. 코드 #include #pragma warning(disable : 4996) int main(void) { int n; long long int ary[92]; ary[0] = 0; ary[1] = 1; scanf("%d",&n); for (int i = 2; i

문제 https://www.acmicpc.net/problem/2747 2747번: 피보나치 수 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 www.acmicpc.net 문제 해결 재귀를 이용하여 0이면 0을 리턴하고 1이면 1를 리턴하고 그외는 n-1,n-2의 함수를 호출하여 구현했다. 코드 #include using namespace std; int fibo(int n){ if(n == 1){return 1;} else if(n == 0){return 0;} return (fibo(n-1)+fibo(n-2)); } int ..

문제 https://www.acmicpc.net/problem/2167 2167번: 2차원 배열의 합 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 www.acmicpc.net 문제 해결 입력받은 그대로 반복문을 만들어서 풀었다. 코드를 보면 이해가 될 것이다. 코드 #include using namespace std; int N,M,map[302][302]; int solve(int x,int y,int dx,int dy){ int result = 0; for(int i = y;i N >> M; for(int i = 1;i map[i]..