1. 문제   2. 접근고려해야 하는 조건은 다음과 같다1번에서 시작해서 N으로 끝내야 한다선택할 수 있는 도시는 최대 M개이다.a도시에서 b도시로 갈 때 경로가 여러개 주어질 수 있다. 최대값만 얻어야 한다 처음 접근은 다익스트라 알고리즘을 사용하는 것이었다. 최대 비용으로 노드를 선택했을 때를 구현하면 될 것 같았다. 하지만 중간에 구현하다가 기내식의 비용이 같을 때는 어떻게 처리하지? 의문이 들었고 그리디적 알고리즘으로 최적의 상황이 해가되는 다익스트라로는 풀 수 없는 것을 깨달았다. 어떻게 풀나 찾아봤더니 DP를 이용하는 문제였다.  DP를 2차원 배열 DP[N][M] 선언하고 도시 N을 M번째로 선택했을 떄의 값을 구해준다.점화식은 다음과 같다` DP[b][M] = Math.max(DP[b][M..

1. 문제 2. 접근 입력값이 최대 10만이고 그래이드는 5개이므로 O(5n)으로 풀면 되지 않을까 생각했다. 처음 접근은 이전의 그레이드와 현재 그레이드를 비교해서 연속하면 누적 카운트를 더해주고, 연속이 끊기면 누적 카운트를 맥스값과 비교해서 갱신한 후 누적값을 초기화 시키는 것이었다. 하지만 틀렸다! 더 좋은 방법은 2차원 배열로 student[6][N]를 만들어서 진행하는 것이다. 처음 student 배열을 0으로 모두 초기화한 후, 차례대로 N번 루프를 돈다. 이때 n은 책상의 수로 입력으로 주어지는 n책상에 대한 그레이드 정보를 이용한다. grage1, grade2를 알아낸 후 이전의 값에 1을 더한다. 누적값을 알아야 하므로 이렇게 하면 변수 하나로 누적값을 관리할 수 있다. 그리고 연결이 ..

문제 링크 21278번: 호석이 두 마리 치킨 위의 그림과 같이 1번과 2번 건물에 치킨집을 짓게 되면 1번부터 5번 건물에 대해 치킨집까지의 왕복 시간이 0, 0, 2, 2, 2 로 최소가 된다. 2번과 3번 건물에 지어도 동일한 왕복 시간이 나오지만 더 www.acmicpc.net 분류 브루트포스 알고리즘, 플로이드–워셜, 그래프 이론, 그래프 탐색, 최단 경로 문제 설명 컴공 출신은 치킨집을 하게 되어있다. 현실을 부정하지 말고 받아들이면 마음이 편하다. 결국 호석이도 2050년에는 치킨집을 하고 있다. 치킨집 이름은 "호석이 두마리 치킨"이다. 이번에 키친 도시로 분점을 확보하게 된 호석이 두마리 치킨은 도시 안에 2개의 매장을 지으려고 한다. 도시는 N 개의 건물과 M 개의 도로로 이루어져 있다..

1. 문제 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 설명 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 현재 (1, 1)에 있고, (N, M)으로 이동하려고 한다. 준규가 (r, c)에 있으면, (r+1, c), (r, c+1), (r+1, c+1)로 이동할 수 있고, 각 방을 방문할 때마다 방에 놓여져있는 사탕을 모두 가져갈..

1. 🐳 문제 [Gold III] 파티 - 1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 문제 설명 N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다. 어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다. 각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학..