본문 바로가기

분류 전체보기

(52)
백준 2193 이친수 https://www.acmicpc.net/problem/2193 위 문제를 풀기위해 n이 2,3,4,5 일때 case를 나누어서 생각하고 있었는데,적다보니 피보나치 수열로 정답이 계산되는 것을 알 수 있었다. #include using namespace std;int main(){ long long dp[91] = {0, }; int n; cin >> n; dp[1] = 1; for (int i = 2; i
백준 1937번 욕심쟁이 판다 https://www.acmicpc.net/problem/1937 #include #include using namespace std;int dx[4] = {0, -1, 0, 1};int dy[4] = {-1, 0, 1, 0};int dp[501][501] = {0, };int tree[501][501] = {0, };int n;bool isInner(int i, int j) { if (i >= 0 && i = 0 && j
(공통문제) n-queens 공통문제로 backtracking의 대표 문제인 n-queens 가 선택되었다. n-queens 를 예전에 답을 본적이 있지만, 역시나.. 이번에도 답을 봐버렸다.이참에 확실히 정리하고 넘어가는 것이 좋을 것 같아, 최대한 자세하게 풀이를 적을 것이다. (내가 이해할 수 있도록) backtracking 이란?backtracking 이란 어떤 노드의 유망성(promising)을 점검한 뒤, 유망하지 않다면 해당 노드의 부모노드로 돌아가(backtracking) 다음 잣기 노드에 대한 검색을 계속 진행하는 과정의 방법이다.(출처 - http://emzei.tistory.com/223 ) n-queen 문제가 무엇인지에 대해선.. 다른 곳에 자세히 나와있으니 그걸 보도록 하고, 문제를 풀기위해선 상태공간 트리..
백준 2292번 벌집 https://www.acmicpc.net/problem/2292 위 문제를 보다보니.. 벌집이 생성 될 때 규칙을 찾을 수 있었다. 첫번째 육각형의 최대 값은 1두번째 육각형의 최대 값은 7세번째 육각형의 최대 값은 19네번째 육각형의 최대 값은 37다섯번째 육각형의 최대 값은 61 즉, 1 7 19 37 61... 순으로 증가하는 셈인데, 여기에 -1을 해주면0 6 18 36 60 으로 6의 배수가 되는 것을 알 수 있었다. 첫째항은 0 * 6 = 0두번째항은 1 * 6 = 1세번째항은 3 * 6 = 18네번째항은 6 * 6 = 36다섯번째항은 10 * 6 = 60이므로, 앞자리 곱셈의 규칙을 찾아내면 되는 것이다. 앞자리의 0 1 3 6 10 의 규칙은 이전 항에서 1 2 3 4 씩 증가되고, 이는..
백준 2163번 초콜릿 자르기 https://www.acmicpc.net/problem/2163 이번 문제는.. 좀 어려운 줄 알았는데, 그렇지 않았다.간단하게 풀이를 말하자면 N * 5 초콜렛이 있을 때, N번 가로로 형태로 하여 초콜릿을 자르면 5칸 짜리 초콜렛이 N줄이 생기게 된다.이 후, 5칸 짜리 초콜렛을 모두 1칸으로 만들면 되는 것이다. 1번째줄 4번2번째줄 4번3번째줄 4번 ... N번째줄 4번이라 생각하며 식을 세우면서 풀고 있었는데.. 가만히 생각해보니2 * 3 초콜릿은 = 5번3 * 3 초콜릿은 = 8번10 * 20 초콜릿은 = 199번 즉, 초콜릿의 너비 - 1 만큼이 최소횟수가 되는 것이다... #include using namespace std;int main(){ int n, m; cin >> n >> m ..
(공통문제) 지그재그 배열 #include #include using namespace std; int* getStartPos (int _startPos, int _n) { int x, y, moveRow, moveCol; int *info = new int[5]; switch (_startPos) { case 1 : info[0] = _startPos; info[1] = _startPos; info[2] = 1; info[3] = 1; info[4] = true; break; case 2 : info[0] = _n; info[1] = _startPos; info[2] = -1; info[3] = 1; info[4] = true; break; case 3 : info[0] = _n; info[1] = _n; info[2] = -1..
백준 1965번 상자넣기 https://www.acmicpc.net/problem/1965 이번 문제를 풀 땐 n번째 마다 최대로 넣을 수 있는 상자를 계산하는 것으로 점화식을 구성하였다. 즉, num[n] = n번째에서 가장 최대로 넣을 수 있는 상자의 수 가 된다.이것을 기준으로, n번째 상자에 왔을 때 (n-1, n-2, n-3, ... 1)번째 상자를 탐색하면서n번째 상자가 n-1번째 상자보다 크면, num[n]을 비교하여 최대값을 갱신해주면 된다. 그리고 처음에 num[n] = 1 로 초기화 시켜준 것은 상자의 배열이 9 8 7 6 5 라면 답은 1이기 때문이다.(간단하게 말하면, 어느 자리에서든 상자에 최소 1개를 넣을 수 있다는 뜻이다.) #include #include #define MAX 1000using nam..
백준 2178번 미로탐색 https://www.acmicpc.net/problem/2178 이 문제에서 도착지점에 도착할 수 있는 최소의 칸 수가 답이라하여, cmath 의 min 함수를 사용할 필요는 없다. 왜냐하면 특정 (n, m) 좌표에 도착할 때는 항상 최소값을 가지기 때문이다. 위의 사항을 주의하고 기본적인 dfs 알고리즘을 적용시키면 답을 도출시킬 수 있다. #include #include #include #pragma warning(disable:4996)using namespace std;int main(){ char map[101][101]; int row, col, d[101][101] = {0, }; int dx[4] = {0, -1, 0, 1}; int dy[4] = {-1, 0, 1, 0}; cin >> ..