https://www.acmicpc.net/problem/21736DFS BFS다 가능한 문제이다.입력으로 주어진 맵에 따라서 돌아다니며 방문할 수 있는 위치에 있는 P의 갯수를 찾으면 된다.전형적인 탐색 문제이므로 아는 방식 그대로 적용해서 풀면 된다.#include #include #include using namespace std;int dx[] = { 1, 0, -1, 0 };int dy[] = { 0, 1, 0, -1 };vector> campus;int N, M;void calculate(int startY, int startX) { int ans = 0; queue> que; que.push(make_pair(startY, startX)); campus[startY].at(startX) = ..

https://www.acmicpc.net/problem/1541연산자가 +와 -로만 구성되어 있다.괄호는 자유롭게 사용할 수 있으므로 가장 작은 수를 만든다고 하면 작은 수에서 큰 수를 빼주면 된다. 여기서 큰 수를 빼주는 방법은 간단하게 첫번째로 나오는 마이너스 연산자의 뒤에 있는 숫자를 다 묶어서 더해주면 된다. 즉 이 문제의 포인트는 첫번째로 나오는 마이너스를 찾아주는 것이다.#include #include using namespace std;int calculate(string input){ string temp; int sum = 0; bool bMinus = false; for (int i = 0; i > input; cout stoi로 숫자들을 뽑아주다가 마이너스 연산자가 나오면 bool ..

https://www.acmicpc.net/problem/18870좌표 압축이란? 간단하게 말해서 존재하는 좌표 중 비교하는 자신보다 낮은 좌표의 갯수를 대신 출력하는 것이다. 입력이 2 4 1 3 이라고 하면 압축 시 1 3 0 2 가 되는 것이다.#include #include #include using namespace std;int main(){ vector list; vector solve; int N; cin >> N; for (int i = 0; i > temp; list.push_back(temp); solve.push_back(temp); } sort(solve.begin(), solve.end()); solve.erase(unique(solve.begin(), solve.end()..

https://www.acmicpc.net/problem/2805간단하게 생각해서 맨 위에서부터 잘라나가면 정답을 찾을 수 있지 않을까? 지만N, M의 범위가 굉장히 크기 때문에 시간 초과가 발생할 것이다. 그렇기 때문에 이분 탐색을 활용해 문제를 풀어야 한다.#include #include #include using namespace std;int N, M;vector list;int solve(){ int answer = 0; int minValue = 0; int maxValue = list[N - 1]; while (minValue midValue) sum += list[i] - midValue; } if (sum > M) { minValue = midValue + 1; ans..

https://www.acmicpc.net/problem/17626DP와 브루트포스를 사용하는 문제이다. 모든 수는 제곱수로 표현되기 때문에 접근을 다음과 같이 진행하였다.26일 경우는 1^2 + 25, 2^2 + 22 ...그렇게 수를 계산하면 남은 숫자 25, 22 등등이 생기는데, 그것은 다시 DP[25], DP[22] 등을 다시 진행하면 된다. 모든 제곱수를 수를 확인하였을 때, 가장 적은 수를 계속 저장하면서 값을 확인하면 된다.#include #include #include using namespace std;int main(){ vector list; int n; cin >> n; list = vector(n + 1, -1); for (int i = 1; i * i n을 입력받은 뒤, n보..

https://www.acmicpc.net/problem/2630예시로 주어진 사진과 함께 생각해보면 2의 배수로 주어지는 N이 나눌때마다 2 / N로 계속 줄어드는 것을 볼 수 있다. 즉 첫 시작점만 정해주게 되면 줄어드는 값을 더해 끝점을 구할 수 있고, 시작점과 끝점 안에 있는 내용을 확인하여 색이 모두 일치하는지 보면 된다.#include #include using namespace std;int N;vector> board;vector answer;void solve(int sX, int sY, int size){ if (size == 0) return; bool bClear = true; int color = board[sY].at(sX); for (int y = sY; y > N; boar..

https://www.acmicpc.net/problem/11727이전 글과 마찬가지로 규칙을 찾았다. N이 1일때 1, 2일때엔 3, 3일때엔 5, 4일때엔 11..짝수일 때에는 전 수의 2배 + 1, 홀수일 때에는 전 수의 2배 - 1로 되어 이 식을 적용하였다.#include #include using namespace std;int main(){ vector list; int n; cin >> n; list.push_back(0); list.push_back(1); for (int i = 2; i

https://www.acmicpc.net/problem/11726규칙을 찾아내면 된다. N이 1일 때엔 방법이 한 개. N이 2일 때엔 방법이 2개, N이 3일 때엔 방법이 3개 ....좀 진행해보면 이전 두 수를 더한 값이 정답이라는 것을 알 수 있다.#include #include using namespace std;int solve(int N){ vector list = vector(1001, -1); list[1] = 1; list[2] = 2; for (int i = 3; i > N; cout

https://www.acmicpc.net/problem/9375 종류에 따라 만들 수 있는 조합의 갯수를 찾아야한다. 예를 들어 모자가 2개, 바지가 3개 있다고 했을 시 가능한 방법은(모자1, 모자2, 모자X) * (바지1, 바지2, 바지3, 바지X) 으로 조합을 만들 수 있다.다만, 모두 입지 않은 경우는 제외해야 하기 때문에 모자X와 바지X를 입은 경우를 빼 주어야 정답이 된다.#include #include using namespace std;int solve(){ map list; int value, answer = 1; cin >> value; for (int i = 0; i > name >> type; if (list.find(type) == list.end()) list.insert..

https://www.acmicpc.net/problem/9095DP는 점화식. 1과 2, 3으로 구성되어 나타내는 방법을 구하는 문제이다.점화식을 생각해 내는 것이 어렵지만 1, 2, 3을 사용하는 점을 생각하여 도출해 내야 한다.#include #include using namespace std;vector answer = vector(12, -1);void cal(){ answer[1] = 1; answer[2] = 2; answer[3] = 4; for (int i = 4; i > T; cal(); for (int i = 0; i > input; cout 하나의 수에 대해 방법을 구할 때에 처음에 1이 오게 되면, 남은 숫자는 N - 1의 방법 합이 된다.2가 오게 되면, 남은 숫자는 N - 2..