전체 글361 [BOJ]14502번: 연구소 www.acmicpc.net/problem/14502 조합을 사용해서 푸는 시뮬레이션 문제입니다. 1. 빈 칸 중에 3칸을 뽑습니다. (조합 사용) 2. 새로 뽑은 3칸을 벽으로 바꾼 뒤 BFS를 돌려서 방문하지 않은 빈 칸을 셉니다. 3. 모든 조합 경우의 수에 대해 2번 값이 최대인 값이 정답입니다. 코드: github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ14502.java 2021. 4. 9. [BOJ]1759번: 암호 만들기 www.acmicpc.net/problem/1759 시뮬레이션 문제입니다. 1. 주어진 문자열을 알파벳 오름차순으로 정렬합니다. 2. C개의 문자에서 L개의 문자를 뽑습니다. 3. 뽑은 L개의 문자가 주어진 조건을 만족하는지 확인합니다. 4. 3번에서 조건을 만족한다면 정답 문자열로 추가합니다. 1번에서 주어진 문자열을 정렬 후 뽑기 시작하므로 앞에서부터 뽑은 순서대로 정답을 구하면 됩니다. 코드: github.com/cotchan/algorithm/blob/main/java/BOJ/BOJ1759.java 2021. 4. 8. [BOJ]15591번: MooTube (Silver) www.acmicpc.net/problem/15591 류트님 풀이(ryute.tistory.com/30)를 참고하여 해결하였습니다. N,Q 제한이 5000으로 작은 편입니다. 때문에 하나의 쿼리를 O(N)에 해결해도 O(QN)에 해결가능합니다. O(N)에 해결할 수 있는 방법은 하나의 쿼리당 BFS를 한 번 돌리면 됩니다. 주어진 동영상 v에 대해서 인접한 정점을 방문하면서 간선 가중치가 k이상인 정점만 방문합니다. 그러면 동영상 v와 연결되어있으면서 가중치가 k미만(== 유사도 k미만)인 정점은 제외됩니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ15591.cc 2021. 3. 31. [BOJ]10655번: 마라톤 1 www.acmicpc.net/problem/10655 수학 문제입니다. 1번부터 N번 체크포인트까지 순서대로 이동한다는 제약이 있습니다. 그러므로 정답 후보들끼리도 하나의 체크포인트를 제외하여도 나머지 경로는 동일합니다. 예시) 1-2-3-4-5 경로가 있다고 가정 1. 2번 체크포인트 제외하는 경우 1-3-4-5 2. 3번 체크포인트 제외하는 경우 1-2-4-5 3. 4번 체크포인트 제외하는 경우 1-2-3-5 즉, x번 체크포인트를 제외한다고 가정하면 x-1번 체크포인트 -> x번 체크포인트 x번 체크포인트 -> x+1번 체크포인트 위 두 경로만 빼면 나머지 경로는 다른 정답후보들과 동일하다는 뜻입니다. 풀이) 1. 1번부터 N번 체크포인트까지의 경로를 전부 구합니다. 2. 2번~N-1번 체크포인트에.. 2021. 3. 30. 이전 1 ··· 36 37 38 39 40 41 42 ··· 91 다음
