백준 문제 풀이34 [백준 1261] 알고스팟 https://acmicpc.net/problem/1261 해설 이 문제는 일반적으로 BFS 나 다익스트라로 풀 것이다. 나는 bfs로 풀면 코드가 복잡해질 것 같아 다익스트라 알고리즘으로 푸는 쪽을 선택했다. 다익스트라로 푸는 방법은 간단했다. (사실 간단하진 않다.) 문제에서 나와있듯이 빈 방은 가중치를 0으로, 벽은 가중치를 1로 잡고 다익스트라로 돌려주었다. ˙˙˙ 소스코드 #include #include using namespace std; const int SIZE = 100; int M, N; int map[SIZE][SIZE]; int minCheck[SIZE][SIZE]; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; using p = pai.. 2020. 3. 25. [백준 1916] 최소비용 구하기 https://acmicpc.net/problem/1916 해설 이 문제는 전에 풀었던 백준 1753 최단경로 문제와 동일하게 다익스트라 알고리즘을 사용해서 푸는 문제이다. 다익스트라의 개념을 모르면 풀기 힘들수도 있으니 다익스트라에 대해 구글링해서 구현법을 꼭 익히고 오길 바란다. 처음 지점으로 다익스트라를 돌리고 마지막에 처음지점과 도착 지점의 거리만 출력해주면 끝이다. ˙˙˙ 소스코드 #include #include #include const int mn = 1e3; const int INF = 1e9; using namespace std; using p = pair; vector g[mn]; int dist[mn]; void init(int n) { for (int i = 0; i < n; i++.. 2020. 3. 25. [백준 1753] 최단경로 https://acmicpc.net/problem/1753 해설 이번 문제는 한 정점에서의 다른 정점들의 최단 거리를 구하는 다익스트라 알고리즘을 적용하는 문제이다. 다익스트라 알고리즘을 구현할 수있다면 바로 풀리는 문제이니 참고바란다. 다익스트라를 모른다면, 풀기 힘들 수도 있으니 구글링으로 다익스트라의 구현법을 어느정도 알고 오는 것을 추천한다. ˙˙˙ 소스코드 #include #include using namespace std; const int mn = 2e4; const int INF = 1e9; vector g[mn]; int dist[mn]; int main(){ int n, m; cin >> n >> m; int k; cin >> k; k--; for(int i=0; i> u >> v >>.. 2020. 3. 25. [백준 1049] 기타줄 https://www.acmicpc.net/problem/1049 해설 이번 문제는 그리디 문제이다. 6줄 세트의 가격 중에서 가장 싼 브랜드를 pp, 낱개 중 가장 싼 브랜드를 ii 로 두었다. i) (n+1) * pp 가 n*ii 보다 작은 경우가 있을 수 있으므로 (n+1)*pp ii) pp와 ii를 적절히 사용하는 n/6*pp + n%6*ii iii) ii로만 n을 만드는 경우 n*ii 총 3가지 경우에서 최솟값을 구해주었다. ˙˙˙ 소스코드 #include using namespace std; int main(){ int n,m; cin >> n >> m; int pp=54321, ii=54321; while(m--){ int a,b; cin >> a >> b; if(a 2020. 3. 25. 이전 1 2 3 4 5 6 7 ··· 9 다음
