https://www.acmicpc.net/problem/12851 이 문제는 BFS를 사용하면 해결할 수 있다. 수빈이가 움직일 수 있는 경우의 수는 3가지다.뒤로 1칸, 앞으로 1칸, 2배 전진하는 경우이다.따라서 dir 배열 속에 {-1, 1, 0}을 넣고 0인 경우 2배 전진하도록 한다. 현재 위치가 동생의 위치인 경우 최소 시간과 현재 시간을 비교하여최소 시간이 더 큰 경우 동생을 찾을 수 있는 수를 1로 초기화 하고 최소 시간을 갱신한다.만약 최소 시간이 현재 시간과 같다면 동생을 찾을 수 있는 수를 1 증가시킨다. #include #include using namespace std;int N, K;int minTime = 987654321;int answer = 0;bool visited[1..
Baekjoon Review
https://www.acmicpc.net/problem/2096 이 문제는 DP를 사용해서 해결할 수 있다. 문제에서 주어지는 가로의 길이는 항상 3이며, 세로의 길이는 N이다.따라서 최소 DP와 최대 DP 배열을 만들고 배열의 크기는 3으로 한다. 항상 이전의 기록을 이용하기 때문에 입력을 받기 위한 크기 3의 배열이 필요하다. #include using namespace std;int N;int score[3];int minDp[3];int maxDp[3];int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>N; int temp0, temp1, temp2; for(int i = 0;i>..
https://www.acmicpc.net/problem/9935 처음 문제를 해결할 때 find 함수와 erase함수를 사용했다.하지만 find 함수에 필요한 시간과 erase함수에 필요한 시간 때문에최대 길이의 문자열일 경우 시간 초과가 발생하였다. 따라서 스택을 사용해서 문제를 해결하였다. 스택을 사용해 문자열을 폭발 시키는 과정은 다음과 같다.1. 스택에 문자열에 있는 문자를 순차적으로 삽입한다.2. 스택에 들어있는 문자의 개수가 폭발 문자열의 길이와 같거나 클 경우폭발 문자열의 길이만큼 스택에서 문자를 꺼낸다꺼낸 문자열과 폭발 문자열이 일치한 경우 스택에서 제거한다. #include #include #include using namespace std;string target;string bomb..
https://www.acmicpc.net/problem/10830 지수가 int 값 범위를 초과할 수 있으므로 거듭 제곱을 하는 과정에서 시간 초과가 발생할 수 있다. 이는 지수 법칙과 나머지 연산의 성질을 이용해서 해결할 수 있다.지수법칙a^(n + m) = a^n + a^m모듈러 성질(a x b) mod c = (a mod c x b mod c) mod c(a * b) % c = (a % c * b % c) % c 지수 법칙 이용 방법짝수인 경우a^8 = a^4 * a^4 = (a^2 * a^2) * (a^2 * a^2) = ((a^1 * a^1) * (a^1 * a^1)) * ((a^1 * a^1) * (a^1 * a^1)) 홀수인 경우a^9 = a^4 * a^4 * a = ..
https://www.acmicpc.net/problem/2447 별은 가운데의 (N/3)×(N/3) 정사각형을 크기 N/3의 패턴으로 둘러싼 형태로 출력해야한다.이는 가운데인 경우 별 패턴을 출력하지 않는 것이고 가운데가 아닌 경우 별 패턴을 출력하면 된다. 별을 출력할 떄는 가운데인 경우 공백을 출력하고 아닌 경우 별을 출력한다.출력을 위해 area에 맞게 별과 공백을 배열에 삽입한다. 별을 그리기 위해 9개로 영역을 나눈다.영역을 9개로 나누기 위해 area/3을 진행하고 시작 위치와 끝 위치를 알려준다.가운데를 나타내기 위해 가운데에 해당하는 경우 pattern 값을 false를 준다. #include using namespace std;int N;char star[6600][6600];void ..
https://www.acmicpc.net/problem/1992 원래 존재하는 image의 값이 다를 경우 4등분 해야 함을 알 수 있다.이는 분할 정복을 사용해 문제를 해결해야 함을 알 수 있다. 자를 때는 왼쪽 위, 오른 쪽 위, 왼쪽 아래, 오른쪽 아래 순으로 잘라야한다.등분은 4등분이기 때문에 area/2를 해준다.quadTree(y, x, area/2);quadTree(y, x + area/2, area/2);quadTree(y + area/2, x, area/2);quadTree(y + area/2, x + area/2, area/2); 배열을 순회하여 같은 문자가 아닐 시에 자르고 같으면 값을 출력해준다. #include using namespace std;int N;char image[6..
https://www.acmicpc.net/problem/1780 종이를 자를 때는 같은 크기의 종이를 9등분 한다.이는 분할 정복을 사용하여 문제를 해결해야 함을 알 수 있다. 종이를 자를 때 N = 9인 경우 크기 3인 종이가 9개 존재하게된다.따라서 원래 종이의 크기가 n인 경우 다음 종이는 n/3이 된다는 것을 알 수 있다. 종이를 자를지 선택할 때는 paper[y][x]의 값이 paper[y부터 y + size][x부터 x + size 값] 에 있는 값이 다를 경우 자른다. 자르지 않는 경우 paper[y][x]에 존재하는 값을 count하면 된다. #include using namespace std;int N;int paper[2200][2200];int onePaper = 0;int zero..
https://www.acmicpc.net/problem/11444 초기 점화식을 사용해 DP로 문제를 해결하고자 하였다.하지만, 문제 조건 중 N의 최대 값이 1,000,000,000,000,000,000인 것을 알게 되었으며실제로 DP로 문제 접근 시 시간 초과가 발생 하였다. 따라서 이 문제는 DP가 아닌 정복 분할 형태로 해결해야한다. 피보나치의 점화식은 다음과 같다.FIBO[N + 2] = FIBO[N-1] + FIBO[N] 위 점화식을 사용해서 2로 분할하면 아래와 같은 수식을 새울 수 있다.F[n] = F[n-1] + F[n-2]F[n] = F[n-1] + F[n-2] + F[n-2] + F[n-3] = 3F[n-2] + 2F[n-3]F[n] = 5F[n-3] + 3F[n-4]F[n] = 8..
