Algorithm283 [BOJ]17088번: 등차수열 변환 www.acmicpc.net/problem/17088 주어진 배열을 등차수열로 만들 수 있는지 물어보는 문제입니다. 각 숫자에 +1, -1, 가만히 놔두기 이렇게 세 가지 연산을 할 수 있으므로 배열의 숫자 중 a1과 an, 두 개에 대해서만 세 연산(+1, -1, +0)을 하면 나오는 경우의 수는 3*3으로 9가지가 나옵니다. 그래서 9가지 경우의 수에 대해 아래와 같은 연산을 해보는 겁니다. 1. a1, an 정하기 2. 공차 구하기 3. 기존의 숫자를 가지고 주어진 공차를 가진 등차수열을 만들 수 있는지 체크 4. 3번을 만족하는 경우의 수 중 최소 연산 수를 리턴 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ17088.py 2021. 2. 23. [BOJ]12908번: 텔레포트 3 www.acmicpc.net/problem/12908 저는 다익스트라로 해결했습니다. 출발점, 도착점, 텔레포트 가능경로 6개 이렇게 총 8개의 노드가 존재하는 그래프로 변환하였습니다. 기본적으로 노드와 노드간의 거리는 abs(y1-y2) + abs(x1-x2) 입니다. 다만, 텔레포트 가능경로끼리의 거리는 10으로 고정됩니다. 이렇게 8개의 노드끼리의 경로를 셋팅해놓고 다익스트라를 돌려서 다익스트라(출발점, 도착점)을 구하면 그게 최단 경로가 됩니다. 코드: github.com/cotchan/algorithm/blob/main/python/BOJ/BOJ12908.py 2021. 2. 23. [BOJ]10282번: 해킹 www.acmicpc.net/problem/10282 주의사항은 3가지입니다. 1. 컴퓨터 의존관계는 단방향 2. 주어진 컴퓨터 c만 감염되는 경우는 0초입니다. 3. 감염된 순서와 무관하게 감염 시간을 묻는 문제이므로 다익스트라로 해결해야 합니다. 코드: github.com/cotchan/algorithm/blob/main/cpp/BOJ/BOJ10282.cc 2021. 2. 8. [BOJ]9370번: 미확인 도착지 www.acmicpc.net/problem/9370 문제를 잘 읽어보셔야 합니다. 출발지 -> 후보지로 가는 최단 경로 중에 주어진 경로 g,h가 포함된 후보지를 고르는 문제입니다. 저는 문제 잘못 읽어서 가장 짧은 후보지 고르는 줄 알고 헤맸습니다. 출발지 s, 후보지 c, 주어진 경로 g,h라고 한다면 1. 출발지에서 다익스트라를 돌립니다. 2. 주어진 경로 g, h에서 다익스트라를 돌립니다. 그리고 두 조건 중 하나를 만족하면 정답입니다. 1. 출발지 → 후보지 거리 == 출발지 → g 거리 + g 거리 → h 거리 + h 거리 →후보지 거리 2. 출발지 → 후보지 거리 == 출발지 → h 거리 + h 거리 → g 거리 + g 거리 →후보지 거리 정답 후보는 최단 경로에 g,h 경로가 포함되어 있음.. 2021. 2. 8. 이전 1 ··· 21 22 23 24 25 26 27 ··· 71 다음
