전체 글 (168) 썸네일형 리스트형 백준 5719 거의 최단 경로 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있�� www.acmicpc.net 다익스트라 한 번 돌리고 최적경로 지우고 다익스트라 한 번 돌리면 풀 수 있는 문제다. 아이디어가 직관적으로 떠오르는데, 구현이 까다로운 문제 edge는 점과 Weight를 동시에 저장한다. trace에 최적 경로를 저장한다. dist는 S로부터 모든 점까지의 최단 거리를 계산한다. /* 거의 최단 경로 */ #include #include #include #de.. 백준 5557 1학년 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net 다이나믹 프로그래밍. 중요한 건 시작할 때 (0,0)으로 시작하면 안된다는 점이다. 이럴 경우 4 0 0 0 0 같은 반례에 걸린다. 무조건 첫 값을 지정해줘야한다. /* 1학년 */ #include #include #include #include #define ll long long int using namespace std; void input(); void solve(); int .. 백준 1162 도로포장 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포�� www.acmicpc.net 양수 weight의 간선으로 이루어진 그래프에서 한 점으로부터 다른 점까지의 최단거리를 구하는 알고리즘은 다익스트라알고리즘이다. 이 문제는 여기서 한 술 더 뜬다. 내가 원하는 간선의 weight를 0으로 만들 수 있다! 이것만 잘 생각하면 일반적인 다익스트라 문제와 똑같다. N개 중에 K개를 고르는 문제는 어떻게 풀어야할까? N개 중에 K개를 고르는 모든 경우의 수를 구할 수도 있다. 즉 next_p.. 이전 1 ··· 30 31 32 33 34 35 36 ··· 56 다음