Hanbit the Developer

https://www.acmicpc.net/problem/16946 16946번: 벽 부수고 이동하기 4 N×M의 행렬로 표현되는 맵이 있다. 맵에서 0은 이동할 수 있는 곳을 나타내고, 1은 이동할 수 없는 벽이 있는 곳을 나타낸다. 한 칸에서 다른 칸으로 이동하려면, 두 칸이 인접해야 한다. 두 칸이 www.acmicpc.net - 관찰 처음에 든 생각은, 모든 벽들부터 시작하는 탐색을 해주는 것이었다. 하지만 이것은 시간복잡도가 너무 크다. 예제 입력 2를 살펴보자. 위와 같이 구분되는 각각의 공간들을 묶어서 값을 저장하고, 이렇게 한 이후에, 모든 벽들에 대해서 (인접한 공간들의 크기의 합) + 1을 해주면 된다. - 풀이 1. 탐색은 2개로 분류된다. 첫번째는 공간의 크기를 조사하는 탐색이며, ..

https://www.acmicpc.net/problem/5373 5373번: 큐빙 각 테스트 케이스에 대해서 큐브를 모두 돌린 후의 윗 면의 색상을 출력한다. 첫 번째 줄에는 뒷 면과 접하는 칸의 색을 출력하고, 두 번째, 세 번째 줄은 순서대로 출력하면 된다. 흰색은 w, 노란 www.acmicpc.net - 관찰 단순히 rotate() 함수 하나 만들어서 cube[6][3][3]의 데이터를 적절히 변화시키기만 하면 된다. 하지만 구현이 그렇게 단순하지는 않다. 총 2개의 사항을 구현해야한다. 첫째로, 하나의 면을 돌렸을 때 영향을 받는 다른 4개의 면의 데이터 변경이며, 두번째로, 돌린 면의 3x3의 회전이다. 또한 clockwise/inverse라는 방향도 고려해야하는데, 사실 clockwise ..

https://www.acmicpc.net/problem/16724 16724번: 피리 부는 사나이 첫 번째 줄에 지도의 행의 수를 나타내는 N(1 ≤ N ≤ 1,000)과 지도의 열의 수를 나타내는 M(1 ≤ M ≤ 1,000)이 주어진다. 두 번째 줄부터 N개의 줄에 지도의 정보를 나타내는 길이가 M인 문자열이 주 www.acmicpc.net - 관찰 여러 경우에 대한 그림을 그려보면 알겠지만, (0, 0)~(N-1, M-1)로 시작하는 순차적인 탐색을 해보면, 이전 탐색과 동선이 겹치는 경우가 있다. 이 경우에는 하나의 '그룹'으로 묶을 수 있으며, 모든 탐색을 마친 뒤 최종적으로 남는 그룹별로 SAFE ZONE을 설치하면 된다. - 풀이 0. count 변수에 '그룹'의 갯수를 저장하며, 이것을 ..

https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net - 관찰 예제 입력 1의 카드들을 정렬해보면 다음과 같다. 2 3 4 5 7 8 9 이제 K번 주어지는 철수가 내는 카드들을 살펴보자. 4를 내면 5가 나와야하고, 1을 내면 2가 나와야한다. -> 이진탐색 lower_bound를 입력값 + 1에 대해 해준다.(4를 냈다면 5를 찾는 탐색을 진행) 다음으로 카드가 1 2 3 4가 있는데, 0을 ..

https://www.acmicpc.net/problem/11401 11401번: 이항 계수 3 자연수 \(N\)과 정수 \(K\)가 주어졌을 때 이항 계수 \(\binom{N}{K}\)를 1,000,000,007로 나눈 나머지를 구하는 프로그램을 작성하시오. www.acmicpc.net #include #define REP(i, a, b) for(int i=(a);i> N >> K; // Get (K!(N-K)!)^1000000005 long long t = getFactorial(K) * getFactorial(N - K) % MOD; long long res = getPower(t, MOD - 2); // res * N! cout

https://www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 $n$, $m$ ($0 \le m \le n \le 2,000,000,000$, $n \ne 0$)이 들어온다. www.acmicpc.net 10 = 2 * 5에서, 2와 5의 승수만을 고려하여 풀 수 있다는 아이디어를 내야한다. nCr = n! / (r! * (n-r)!)의 각각의 팩토리얼에서 2, 5의 승수를 가져와서 연산을 해주면 된다. 예를 들어, 5C3 = 5!/(3!*2!) = (1*2*3*4*5) / ((1*2*3) * (1*2))에서 5!, 3!, 2!에는 각각 2^1, 5^1 / 2^1 / 2^1가 포함되며 2^(-1), 5^0이므로 0의 개수가 0이다. 만약 어떤 조합에서 2^..

https://www.acmicpc.net/problem/17298 17298번: 오큰수 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에 수열 A의 원소 A1, A2, ..., AN (1 ≤ Ai ≤ 1,000,000)이 주어진다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { int var; int index; struct Node* next; }Node; typedef struct Stack { int size; Node* top; }Stack; Node* getNode(int var, int index) { Node* res = malloc(sizeof..

https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct Node { struct Node* prev; struct Node* next; int value; }Node; Node* getNode(int value) { Node* newNode = malloc(sizeof(Node)); newNode->value = value; return ..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) typedef struct TwoInt { int n1, n2; }TwoInt; void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } TwoInt divideNumsWithPivotAndGet..

https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net #include #include #pragma warning(disable:4996) void printNumbers(int* nums, int length) { for (int i = 0; i < length; i++) printf("%d\n", nums[i]); } void doMerge(int* nums, int left, int right) { int mid = (left + right) / 2; ..