[백준 1780] 종이의 개수 [C]
풀이 9등분을 하고, n/3만큼 좌표를 (x, y) 증가시켜 Divide and Conquer 하면 된다. N만큼의 종이가 모두 같을 때, 탐색을 중단해야 하므로 중단 조건을 함수로 만들어 풀이했다. 소스코드 #include int paper[2187][2187], I[3]; int all_same_paper(int x, int y, int n){ int temp = paper[x][y]; for (int i = x; i < x+n; i++) for (int j = y; j < y+n; j++) if (paper[i][j] != temp) return 0; return 1; } void division(int x, int y, int n){ if (all_same_paper(x, y, n)) I[pape..
2021. 8. 9.
[백준 11727] 2×n 타일링 2 [C]
풀이 "백준 11726, 2×n 타일링" 문제와 비슷하다. 심지어 정답도.. 2x1 타일을 1, 1x2 타일을 2, 2x2 타일을 T라고 가정할 때 다음과 같이 나타낼 수 있다. N 타일 dp[1] 2 11 2, T 3 3 111 12,1T 21,2T 5 4 1111 112,11T 121,1T1 211,T11 22,TT 2T,T2 11 5 11111 1112,111T 1121,11T1 1211,1T11 2111,T111 122,1TT 212,T1T 221,TT1 12T,1T2 21T,T12 2T1,T21 21 6 " 43 7 " 85 8 " 171 N번째 방법의 수는 "2 * (N-2번째 방법의 수) + (N-1번째 방법의 수)" 와 같음을 알 수 있다. 소스코드 #include #define MOD 1..
2021. 8. 8.
[백준 18870] 좌표 정렬 [C/C++]
풀이 입력받은 좌표들을 오름차순으로 정렬하고, 중복을 제거했을 때, 각 요소들이 몇 번째인지 출력하는 문제다. 입력받은 수들을 두 벡터에 저장하고, v2는 오름차순으로 정렬 후, 중복을 제거했다. 중복된 수가 제거된 v2에서 lower_bound()를 사용하면, 원하는 결과를 얻을 수 있다. 소스코드 #include #include #include using namespace std; int main(){ int N, temp; scanf("%d", &N); vector v1(N), v2(N); for (int i = 0; i < N; i++){ scanf("%d", &temp); v1[i] = v2[i] = temp; } sort(v2.begin(), v2.end()); v2.resize(unique(..
2021. 8. 8.
