lastknight00

문제 링크 : [백준]도로포장(1162) 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로를 연결짓는 두 도시와 도로를 통과하 www.acmicpc.net 문제 설명 N개의 노드와 M개의 양방향 간선 정보가 주어집니다. 이 때, 1번 노드에서 N번 노드로 이동하는데, K개의 간선의 비용을 0으로 변경 할 수 있습니다. 1번 노드에서 N번 노드까지의 최단거리를 구하세요. 입력 N(노드의 갯수, 1

문제 링크 : [백준]기업투자(2662) 2662번: 기업투자 어떤 투자가가 여러 기업들에게 돈을 투자해서 최대의 이익을 얻고자 한다. 단, 투자는 만원 단위로 할 수 있으며 각 기업은 많이 투자할수록 많은 이익을 투자가에게 돌려준다. 돈을 투자하지 � www.acmicpc.net 문제 설명 기업별로 투자 금액 별 수익금이 주어집니다. N원을 투자하여 최대로 수익을 얻을 수 있는 금액과 어떤 기업에 얼마를 투자해야 하는지 구하세요. 입력 N(투재 금액, 1

문제 링크 : [백준]컨닝(1014) 1014번: 컨닝 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 문제 설명 N * M 의 격자가 주어지고, 각 칸에는 학생이 앉을 수 있는 경우(.)와 앉을 수 없는 경우(x)가 주어집니다. 이때, 모든 학생이 자신과 인접한 왼쪽, 오른쪽, 오른쪽 위 대각선, 왼쪽 위 대각선에 자리를 비우도록 하여 최대한 많은 사람을 앉게 하는 경우, 몇 명까지 앉힐 수 있는지 구하세요. 입력 T(테스트 케이스의 수) N(격자의 세로 크기, 1

문제 링크 : [백준]미로에 갇힌 건우(18224) 문제 설명 N * N 지도가 주어집니다. 0은 빈 칸, 1은 벽입니다. (1,1)에서 출발하여, (N,N)까지 이동하는데, 벽은 밤에만 넘어갈 수 있고, 진행 방향으로 이어진 벽을 한번에 넘어가야 합니다. 벽을 타고 나면서 지도를 벗어나는 경우는 이동할 수 없습니다. 밤/낮에 몇칸을 이동 할 수 있는지가 주어졌을 때, 목적지로 가장 빠르게 이동하였을 때, 몇번째 날의 낮/밤 여부를 구하세요. 입력 N(지도의 크기, 1 m;m--; for(i=0;id[i][j]; q.push(N(1,m,0,0,1)); v[0][0][1][m]=1; while(!q.empty()){ N c=q.front();q.pop(); if(c.x==n-1&&c.y==n-1){ cout

문제 링크 : [백준]전구(2550) 문제 설명 스위치와 매핑되는 전구들의 입력이 주어집니다. 스위치를 눌러 전구를 켜는데, 선이 교차되는 경우에는 켜지지 않습니다. 최대한 많은 전구를 켤 때의 갯수와 그때 눌러야 할 스위치 번호를 구하세요. 입력 N(전구의 갯수, 1

문제 링크 : [백준]연속합 2(13398) 문제 설명 N개의 수열이 주어질 때, 연속된 구간의 합 중 최대값을 구하세요. 단, 연속합을 구할 때, 하나의 수를 제외하고 연속합을 구할 수 있습니다. 입력 N(수열의 갯수, 1

문제 링크 : [백준]본대 산책2(12850) 문제 설명 그래프가 주어져있고, 1번 노드에서 출발하여, N번 이동해서 1번 노드로 돌아오는 경우의 수를 구하세요. 입력 N(이동횟수, 1 1); D ret; for(int i=0;i

문제 링크 : [백준]Dance Dance Revolution(2342) 문제 설명 두 발이 처음에는 위치 0에서 시작합니다. 왼쪽 발과 오른쪽 발을 주어진 위치(1,2,3,4)로 옮겨야 하며, 두 발중 아무 발이나 옮길 수 있습니다. 단, 옮긴 후, 두 발이 같은 위치에 있으면 안됩니다. 발을 옮길 때마다 아래와 같이 비용이 발생합니다. 0 -> 다른 곳 : 2 1 3, 2 4 : 4 같은 곳을 다시 밟는 경우 : 1 그 외 : 3 밟을 곳이 주어진다면 모두 밟는 경우 중 최소 비용을 구하세요. 입력 Bi(밟을 판의 위치, 0인 경우 종료, 최대 100,000개를 초과하여 주어지지 않습니다.) 1 2 2 4 0 출력 8 카테고리 #DP 시간 복잡도 상한 O(NlongN) 해결 방법 발판이 주어지면, 두..