알고리즘/백준

[백준 17069] 파이프 옮기기 2 C++ (Bottom-up 방식)

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 이번에는 앞에서 포스트 올린 다이나믹 Top-down방식이 아닌, Bottom-up 방식으로 다이나믹 문제를 풀어보겠습니다. Top-down은 아래 링크를 참고 하시면 됩니다. https://rolypolytoy.tistory.com/17 [백준 17069] 파이프 옮기기 2 C++ (Top-down 방식) https://www.acmicpc.net/problem/1706..

[백준 17069] 파이프 옮기기 2 C++ (Top-down 방식)

https://www.acmicpc.net/problem/17069 17069번: 파이프 옮기기 2 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 파이프 옮기기 1에 이어 이번에는 파이프 옮기기 2를 풀이하려고 합니다. 문제풀이 앞에서 나온 '파이프 옮기기 1'의 경우, 출력 조건에 '방법의 수는 항상 1,000,000보다 작거나 같다.'의 조건이 있어 1초 이내로 다 풀 수 있는 문제였습니다. 브루트 포스로 경우의 수를 다 지정하여 갈 수 있는 모든 방법을 다 탐색하면 됐었습니다. 하지만, 이번에는 입력 값이 무려..

[백준 17070] 파이프 옮기기 1 C++

https://www.acmicpc.net/problem/17070 17070번: 파이프 옮기기 1 유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 www.acmicpc.net 문제풀이 이 문제는 입력이 16이 제한이므로 느낌에, 가능한 모든 경우의 수를 구해서 푸는 브루트포스 문제라고 느낌이 들었습니다. 1초를 약 for문 1억번을 돌린다고 생각했을 때, 16x16은 256칸이지만, 1, 2에서 시작하기 때문에 15 x 15 = 225 사실 벽이 없을 때 가정을 하면, 약 O(2^225)라고 생각하지만, 이 수는 천문학적인 수라서 안되고, 아마..

[백준 16922] 로마 숫자 만들기 C++

https://www.acmicpc.net/problem/16922 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net 문제풀이 이 문제를 보자마자 자기 자신은 중복은 되지만 순서간의 중복을 허용하지 않아한다고 생각했습니다. 그래서 자기 자신은 중복으로 수열이 나올 수 있지만, 순서 간에는 중복이 허용하지 않도록 프로그래밍 했습니다. 단순히 풀려고 헀는데, 아마 로마 숫자를 다 더해서 표현하는 것이기 때문에 다 더했을 때 중복이 있어서 처음 짜자마자 돌렸을 때 마지막 케이스가 정답이 안맞았습니다. 입력 2까지는 다 맞았지만, 입력 10에서 모두 합했을 때 중복으로 나올 수 있는 경우의 수도 체크해주어야 한다는 ..

[백준 10971] 외판원 순회 2 C++

https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 문제풀이 W[i][j]는 i -> j로 가는 비용을 말합니다. 만약 1, 2, 3 의 도시가 있다면 모든 도시를 모든 방법으로 방문해보면 됩니다. 이 문제는 W[i][i] i,i 즉 자기 자신은 0입니다. 그리고 W[i][j] i -> j로 가는 방법 중에 경로가 없으면 0으로 표시합니다. 이 문제는 경로가 없을 때를 꼭 고려해주어야지만 정답을 맞출 수..

[백준 10974] 모든 순열 C++

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 문제 : N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. 입력 : 첫째 줄에 N(1 n; for (int i = 0; i > a[i]; } go(0); cout