목록백트래킹 (50)

1일1알

백준 3980번 선발 명단 C++

https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 백트래킹, 능력치가 0이면 배치할 수 없다는 것이 핵심 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; vector abilities; ..
알고리즘 2023. 1. 3. 12:35
백준 6443번 애너그램 C++

https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 전체 문자열에 대해 백트래킹을 시도하면 시간초과가 나서 알파벳 개수에 대해 백트래킹으로 하니까 중복, 정렬 문제도 자연스럽게 해결이 되도록 풀렸다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #i..
알고리즘 2022. 12. 17. 12:37
백준 2992번 크면서 작은 수 C++

https://www.acmicpc.net/problem/2992 2992번: 크면서 작은 수 정수 X가 주어졌을 때, X와 구성이 같으면서 X보다 큰 수 중 가장 작은 수를 출력한다. 수의 구성이 같다는 말은, 수를 이루고 있는 각 자리수가 같다는 뜻이다. 예를 들어, 123과 321은 수의 구성이 www.acmicpc.net 백트래킹을 이용해서 문제를 해결하였다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; s..
알고리즘 2022. 12. 4. 11:20
백준 21772번 가희의 고구마 먹방 C++

https://www.acmicpc.net/problem/21772 21772번: 가희의 고구마 먹방 첫 번째 줄에 맵의 세로 크기 R, 가로 크기 C, 가희가 이동하는 시간 T가 주어집니다. 두 번째 줄부터 R+1번째 줄까지 길이가 C인 문자열이 주어집니다. 주어지는 문자열에 있는 문자는 가희를 www.acmicpc.net 백트래킹 + bfs 를 이용해서 해결하였다. 이미 방문했던 곳이라도 다시 방문하는게 핵심인 것 같다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespac..
알고리즘 2022. 12. 3. 12:45
백준 10974번 모든 순열 C++

https://www.acmicpc.net/problem/10974 10974번: 모든 순열 N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오. www.acmicpc.net 백트래킹 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; int n; vector ans; vector visited; void BT(int size) { if (size >= n) { for (au..
알고리즘 2022. 10. 11. 09:44
백준 2661번 좋은수열 C++

백트래킹을 진행할때 1,2,3 순서대로 채워주면서 채운다음에 나쁜 수열인지 검사한다. 나쁜 수열이면 걸러주고 좋은 수열만 계속 백트래킹을 진행시키다가 n만큼 채워지면 그게 제일 작은 좋은 수열이다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using int64 = long long; char chs[3] = { '1','2','3' }; int n; void BT(string str) { int line = str.length() - 2; int len ..
알고리즘 2022. 8. 22. 09:51
이전 Prev 1 2 3 4 5 6 ··· 9 Next 다음