펭로그

문제링크 : https://boj.kr/11726 시뮬레이션을 해보면 아래 그림과 같이 규칙을 찾을 수 있다.하나의 타일을 1*2로 고정 시키면 N-1의 모든 케이스를 적용할 수 있고두개의 타일을 2*1 두개로 고정 시키면 N-2의 모든 케이스를 적용할 수 있다. 하지만, 여기서 신기한 점은 1, 2, 3, 5.... 피노나치 수열과 동일한 문제임을 알 수 있다. 12345678910111213141516171819202122232425// BOJ 11726 2xn 타일링#include using namespace std; int dp[1001]; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen..

문제링크 : https://boj.kr/3048 개미 그룹이 서로 -> 는 소문자 str[n1 - i]; str[n1 - i] = str[n1 - i] - 'A' + 'a';}for (int i = n1; i > str[i];cs 12345678910111213141516171819202122232425262728293031323334353637383940414243444546// BOJ 3048 개미#include #include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); freopen("../input.txt", "r", stdin); int n1, n2, cnt; c..

문제링크 : https://boj.kr/11559 1. 블럭은 4개 이상 모였을 때 터짐2. 동시에 터지는 것은 하나의 연쇄 단계임3. 한 연쇄 단계에 블럭이 터진 이후 중력에 의해 블럭이 아래로 내려감 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124// BOJ 11559 Puyo Pu..

문제링크 : https://boj.kr/6359 DP 문제라고 한다.왜 DP 문제인지는 잘 모르겠지만 DP로 풀지 않으면 정말 쉽게 풀린다. N이 5라고 가정하고 시뮬레이션을 해보자.0은 문이 닫힌 상태를 1은 문이 열린 상태를 의미한다. 맨 처음0 0 0 0 0 1라운드1 1 1 1 1 2라운드1 0 1 0 1 3라운드1 0 0 0 1 4라운드1 0 0 1 1 5라운드1 0 0 1 0 이쯤 하면 규칙을 찾을 수 있다.각 라운드에 해당하는 숫자만큼의 배수를 찾아서 1 → 0 / 0 → 1 으로 바꿔주면 된다. 12345678910111213141516171819202122232425262728// BOJ 6359 만취한 상범#include #include using namespace std; int ma..

문제링크 : https://boj.kr/1010 이 문제는 M개의 사이트에 N개의 다리를 놓는 가지수를 구하면 되는 문제로 조합을 이용하여 풀었다.MCN = M! / ((M-N)! * N!) 을 구현하면 된다.6C4를 구하는 경우 (6*5*4*3*2*1) / ( (2*1) * (4*3*2*1) ) 인데 (4*3*2*1)에 해당하는 N!이 약분되어 (6*5) / (2*1)인 것을 중학교때 많이 배웠을 것이다. (M-N)!과 N! 중에서 더 많은 숫자를 제거할 수 있는 값을 고르면 되고 이를 그대로 식으로 표현하면 된다. 123456789101112131415161718192021222324252627282930// BOJ 1010 다리 놓기#include using namespace std; int mai..

문제링크 : https://boj.kr/1929 BOJ 2581 소수 문제랑 완전 동일한 문제라고 할 수 있다.소수는 어떤 수 N의 약수가 1과 자기 자신만 가지는 숫자를 의미한다.소수를 구하는 것은 정말 어렵지만 '판별'은 가능하다.자기 자신보다 작은 정수 중에서 약수가 존재하는지를 2~N까지 반복하면 된다.하지만, 약수는 N의 제곱근 보다 큰 숫자는 절대로 나올 수 없다. N의 제곱근 보다 큰 정수에 어떤 정수를 곱하면 이미 N보다 커지기 때문이다. 따라서 N의 제곱근 범위까지만 구하면 된다.하지만 이 방법은 소수를 판별하는 방법이지 소수를 구하는 방법이 아니다.어떤 범위의 숫자가 주어졌을때 소수인지 아닌지를 판별하려면 1~N의 제곱근 까지 계산해야 하는데 이 것을 주어진 범위만큼 반복해야 하기 때문..

문제링크 : 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(..