펭로그

문제링크 : https://boj.kr/3055 BFS를 이용하여 풀이한 시뮬레이션 문제이다.다른 사람들 이야기를 들어보면 굳이 BFS를 이용하고 풀지 않아도 되는 것 같다.(물이 차오르는 시간들을 저장한 배열을 따로 만들면 되는듯 하다.) 아무튼 이 풀이는 BFS!! BFS로 풀이를 고려한다면1. 고슴도치가 비버굴을 찾기 위한 BFS2. 물이 차오르는 BFS동시에 2개의 BFS를 돌려야 한다. 하지만, 문제의 조건에서 '고슴도치는 물이 찰 예정인 칸으로 이동할 수 없다.'라고 하였기 때문에물이 차오르는 BFS를 먼저 선행하고 고슴도치의 BFS를 후행하는 식으로 돌리면 된다.그렇게 하기 위해선 같은 큐 안에 '물'을 먼저 넣어서 돌리고 '고슴도치'를 뒤이어서 넣으면 된다. 입력시 물일 경우 큐에 넣고 고..

https://boj.kr/1547 간단한 시뮬레이션 문제로 배열의 value를 swap을 해주기만 하면 끝 12345678910111213141516171819202122232425// BOJ 1547 공#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int cup[] = {0, 1, 0, 0}; int cnt; cin >> cnt; while(cnt--){ int a, b, tmp; cin >> a >> b; tmp = cup[a]; cup[a] = cup[b]; cup[b] = tmp; } ..

문제링크 : https://boj.kr/3190 N*N의 정사각 보드에 빈칸은 0, 사과는 1, 뱀은 2로 표시해주었다.뱀이 이동할 때 꼬리부터 없어진다는 규칙 때문에 뱀의 몸통은 큐(Queue)를 이용하여 저장하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374// BOJ 3190 뱀#include #include #include using namespace std; // 방향변화const int dx[] = {0,1,0,-1};const int dy[] = {1,0,-1,0}; struct pt..

문제링크 : https://boj.kr/14499 이 문제는 약간의 노가다 문제라고 할 수 있겠다.주사위를 굴릴 때마다 주사위에 써진 숫자의 순서가 뒤바뀌기 때문이다. 방향이 전환 되었을 때마다 어떻게 바뀌는지 전개도를 직접 바꿔보면 아래와 같이 표현 가능하다. 이러한 전개도를 기반으로 다음과 같이 배열을 만들어주고1234567const int s[5][6] = { {1, 2, 3, 4, 5, 6}, // 0 기본 {4, 2, 1, 6, 5, 3}, // 1 동쪽 {3, 2, 6, 1, 5, 4}, // 2 서쪽 {5, 1, 3, 4, 6, 2}, // 3 북쪽 {2, 6, 3, 4, 1, 5} // 4 남쪽};cs 주사위가 재배치 되었을때 재배치 작업을 거쳐주면 된다.1234567void update(..

문제링크 : https://boj.kr/11048 위 그림과 같이 3방향으로 이동하면서 경로 상의 최대 값을 찾는 문제이다. 단계를 계속 진행해서 마지막까지 가게 되면 계산이 가능한 방향은 위 그림처럼 된다.DP 식으로 표현해보면 다음과 같이 표현 가능하다.DP[N][M] = MAX (DP[N-1][M], DP[N][M-1], DP[N-1][M-1]) + 자기자신값 12345678910111213141516171819202122232425262728293031323334// BOJ 11048 이동하기#include #include using namespace std; int max(int a, int b) { return a > b ? a : b;} int max(int a, int b, int c) {..

문제링크 : https://boj.kr 시뮬레이션 문제로 주어진 조건에 맞게 그대로 풀어내려가면 되는 문제이다.문제 접근 방법은 DFS 방식이랑 크게 차이 없지만 DFS로 풀면 스택이 계속 쌓이기 때문에 이렇게 푸는 편이 더 좋지 않을까 생각한다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778// BOJ 14503 로봇 청소기#include #include using namespace std; struct pt{ int x, y, d;}; const int dx[] = {-1, 0, 1, ..

문제링크 : https://boj.kr/7562 (시작점) -> (끝점)까지 나이트가 갈 수 있는 경로의 최단거리를 구하는 문제로 이동 가능한 8방향으로 BFS를 돌리면 풀 수 있다.장애물 없이 오로지 도달만 하면 되기 때문에 방문 체크를 위한 배열 visited만 선언해주었다.방문 조건은 (0,0) ~ (len-1, len-1)의 범위로만 한정하였다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960// BOJ 7562 나이트의 이동#include #include #include using namespace std; const int dx[] = {-2,..

문제링크 : https://boj.kr/9465 DP 문제로 아래의 3가지 케이스로 계산할 수 있다. case 1.o xx o case 2.o x xx x o case 3.x x o xo x x o 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647// BOJ 9465 스티커#include #include int max(int a, int b) { return a > b ? a : b;}int max(int a, int b, int c){ return max(max(a, b), c);} using namespace std; int main() { ios_base::sync_with_stdio(false)..

문제링크 : https://boj.kr/2805 1. 동적계획법(DP)을 이용한 풀이법 : 시간복잡도 O(N)나무의 길이가 제일 큰 것부터 시작하여 한단계씩 내려오면서 누적 합이 입력에서 주어진 값보다 클 때까지 구하는 방법으로 풀었다.입력 받은 값들을 내림차순으로 정렬하고 맨 첫번째 인덱스에 해당하는 값부터 시작하여 1씩 높이를 빼가면서 계산했다. 나무의 높이(arr[N])가 기준 높이(result)보다 높은 부분 까지만 인덱스를 탐색하고 기준 높이 이하(arr[N] - result)가 0 이하인 값들)가 나오면 현재 누적 잘린 나무들의 합이 정답보다 작다면 계속 루프를 진행한다.이때, 높이를 1씩 빼게되면 현재까지 진행해왔던 나무들의 높이가 각각 1씩 추가되기 때문에 sum += ptr 구문을 넣어 ..

문제 링크 : https://boj.kr/2293 1234567891011121314151617181920212223242526272829303132// BOJ 2293 동전1#include using namespace std; int dp[10001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int num, result; cin >> num >> result; vector coin(num + 1); vector dp(result + 1, 0); for (int i = 1; i > coin[i]; dp[0] = 1; for (int cn :..