BOJ 14585 - 사수빈탕 문제 링크https://www.acmicpc.net/problem/14585 문제 해결 1. (0, 0) 에서부터 x 좌표가 증가하는 방향과 y 좌표가 증가하는 방향으로만 이동한다. → Dynamic Programming으로 해결할 수 있음을 알 수 있는 부분. 주의할 점 || 생각해볼 점 1. M의 값이 1,000,000이고 N의 값이 300이면 M*N = 3억이 될 수 있으므로 (int형 범위를 초과할 수 있으므로) 자료형은 long long을 선택한다. 2. 매 시간마다 1씩 줄어드는 것을 따로 구현할 필요가 없이 가로와 세로의 값을 최초 사탕의 값에서 빼주면 된다. ( a[x][y] - (x+y) ) 3. 처음 문제를 봤을 때, BFS(넓이 우선 탐색)를 이용해서 문제를 해결하려 했다. 그러나 문.. 더보기 DFS를 이용해서 사이클 탐색 쉽게 설명하면 순환하는 정점들의 집합을 V(G)이라 할 때, ①인접한 정점들의 간선은 그래프 내에 있어야하고,②사이클 내에서 정점은 중복되면 안된다. ※ 저 중에서 닫힌 보행이라는 말과 혼동하지 말라는 데, 닫힌 보행은 단순히 시작점과 끝점이 같은 경로를 말한다. 알고리즘 무향 그래프와 유향 그래프 모두 DFS(깊이 우선 탐색) 알고리즘을 이용해서 탐색할 수 있다. - 무향 그래프 : 시간 복잡도 O(N) - 유향 그래프 : 강결합 요소와 위상 정렬로도 구할 수 있다. 참고 링크 - http://vjerksen.tistory.com/32 (BOJ 2668 - 숫자고르기) - http://vjerksen.tistory.com/33 (BOJ 2526 - 싸이클) 참고 사이트 - https://ko.wikip.. 더보기 BOJ 1072 - 게임 문제 링크https://www.acmicpc.net/problem/1072 문제 해결 1. 처음 주어진 게임 수와 승리 수를 토대로 승률 (winning_rate)을 구한다. 2. 앞으로 치뤄야 할 경기의 수를 Parametric Search로 구한다. 주의할 점 || 생각해볼 점 1. 앞으로 계속 이길 예정이므로 게임을 치루게되면 승률은 99~100% 사이가 된다. 이미 승률이 99% 이상이면 더 이상 오를 승률이 없게된다. 이 때 문제에서 요구한대로 ' -1 ' 을 출력한다. 참고 - ※ 정확하고 부드러운 태클은 언제나 환영입니다. 더보기 이전 1 ··· 19 20 21 22 23 24 25 ··· 32 다음
