[백준] 14500번 : 테트로미노 - C++
백준 14500번 : 테트로미노 등급 : Gold IV 14500번: 테트로미노 (acmicpc.net) 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 사용 알고리즘 : Brute-Force, DFS, Backtracking 사용 자료구조 : Vector DFS와 백트래킹, 그리고 예외 케이스에 대한 탐색으로 구현할 수 있다. 위의 사진을 보았을 때, 테트로미노의 5개의 도형 중 마지막 도형만 제외하면 모두 DFS로 탐색이 가능하다. 즉, 5번째 도형 = 예외 케이스. 이 부분만 유의하면 어렵지 않게 구현이 ..
백준 3020번 : 개똥벌레 등급 : Gold V 3020번: 개똥벌레 (acmicpc.net) 3020번: 개똥벌레 개똥벌레 한 마리가 장애물(석순과 종유석)로 가득찬 동굴에 들어갔다. 동굴의 길이는 N미터이고, 높이는 H미터이다. (N은 짝수) 첫 번째 장애물은 항상 석순이고, 그 다음에는 종유석과 석순이 www.acmicpc.net 사용 알고리즘 : - 사용 자료구조 : Vector 이분 탐색이라고 쓰여있지만 딱히 이분 탐색 알고리즘을 사용하지 않아도 되는 문제이다. 첫 접근은 이중 for문으로 각 자리를 계산하는 방식으로 진행하였다. → TLE 때문에 석순과 종유석의 벡터를 각각 구현해주고, 각각의 for문을 누적 합으로 구현했다. Top vector : 종유석 지정 벡터. Bottom vecto..