알고리즘/백준
-
[알고리즘/DP] 백준 11726번: 2xn 타일링 - C++알고리즘/백준 2020. 12. 12. 21:51
www.acmicpc.net/problem/11726 11726번: 2×n 타일링 2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다. www.acmicpc.net 다이나믹 프로그래밍을 이용하였다. #include using namespace std; int d[1001]; int main() { int n; cin >> n; d[0] = 1; d[1] = 1; for (int i = 2; i
-
[알고리즘/DP] 백준 1463번: 1로 만들기 - C++알고리즘/백준 2020. 12. 12. 21:49
www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 다이나믹 프로그래밍을 이용하였다. #include using namespace std; int d[1000001]; int main() { int N; cin >> N; d[1] = 0; for (int i = 2; i d[i/2] + 1) { d[i] = d[i / 2] + 1; } if (i % 3 == 0 && d[i] > d[i / 3] + 1) { d[i] = d[i / 3] + 1; } } cout
-
[알고리즘] 백준 1261번: 알고스팟 - C++알고리즘/백준 2020. 12. 12. 21:47
www.acmicpc.net/problem/1261 1261번: 알고스팟 첫째 줄에 미로의 크기를 나타내는 가로 크기 M, 세로 크기 N (1 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 미로의 상태를 나타내는 숫자 0과 1이 주어진다. 0은 빈 방을 의미하고, 1은 벽을 의미 www.acmicpc.net #include #include using namespace std; int a[555][555]; int d[555][555]; int dx[] = {0, 0, -1, 1}; int dy[] = {-1, 1, 0, 0}; int N, M; int main() { scanf("%d", &M); scanf("%d", &N); for (int i = 0; i < N; i++) { for (in..
-
[알고리즘] 백준 2580번: 스도쿠 - C++알고리즘/백준 2020. 12. 12. 21:46
www.acmicpc.net/problem/2580 2580번: 스도쿠 스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루 www.acmicpc.net #include using namespace std; int s[9][9]; bool c[9][9], c1[9][9], c2[9][9]; int square(int i, int j) { return (i / 3) * 3 + (j / 3); } void sdo(int z) { if (z == 81) { for (int i = 0; i < 9; i++) { for (int j = 0; j < 9; j++) { cout
-
[알고리즘] 백준 9663번: N-Queen - C++알고리즘/백준 2020. 12. 12. 21:43
www.acmicpc.net/problem/9663 9663번: N-Queen N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다. N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오. www.acmicpc.net #include using namespace std; bool a[15][15]; int N, ans; bool check(int row, int col) { int x, y; x = row - 1; y = col; while(x >= 0) { if (a[x][y]) return false; x--; } x = row - 1; y = col - 1; while (x >= 0 && y >= 0) { if (a[x][y]) ret..
-
[알고리즘] 9019번: DSLR - C++알고리즘/백준 2020. 12. 12. 21:42
www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net #include #include #include using namespace std; int main() { int T; cin >> T; while (T--) { int A, B, now, next; cin >> A >> B; bool check[10000] = { false, }; char how[10000] = { '\0', }; int from[10000] = { 0, }; queue reg..
-
[알고리즘] 백준 10971번: 외판원 순회 2 - C++알고리즘/백준 2020. 12. 12. 21:40
www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net #include #include #include using namespace std; int main() { int N; cin >> N; vector w(N, vector(N, 0)); vector d(N); for (int i = 0; i > w[i][j]; } ..
-
[알고리즘] 백준 10819번: 차이를 최대로 - C++알고리즘/백준 2020. 12. 12. 21:38
www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net #include #include #include using namespace std; int calculation(vector &a) { int calc = 0; for (int i = 1; i > N; vector a(N); for (..