목록분류 전체보기 (217)
Study hard
www.acmicpc.net/problem/2616 2616번: 소형기관차 첫째 줄에 기관차가 끌고 가던 객차의 수가 입력된다. 그 수는 50,000 이하이다. 둘째 줄에는 기관차가 끌고 가던 객차에 타고 있는 손님의 수가 1번 객차부터 차례로 입력된다. 한 객차에 타고 있� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[x][y]: x번째 소형 기관차가 y번째 객차를 끌고갈 경우 x번째 기관차가 y번째 객차를 끌고가는 경우와 끌고가지 않는 경우를 비교해 줘야 한다. train[]에 해당 인덱스까지의 누적 인원수를 저장한다. res = max(solution(x,y+1), train[y + M - 1] - train[y - 1] + solution(x+1,y+M)) #inclu..
www.acmicpc.net/problem/2281 2281번: 데스노트 첫째 줄에 n(1 ≤ n ≤ 1,000), m(1 ≤ m ≤ 1,000)이 주어진다. m은 노트의 가로 칸의 개수(폭, 너비)이다. 다음 n개의 줄에는 각 사람의 이름의 길이가 노트에 적어야 할 순서대로 주어진다. 각 길이는 m� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[name][len] : 현재 쓰려는 이름의 인덱스, 해당 줄에 지금까지 쓰인 글자 수 다음 줄로 넘어가는 경우와 넘어가지 않고 그 줄에 쓰는 경우를 비교한다. #include #include //memset #include //min using namespace std; int n, m; int Name[1001]; int dp[10..
www.acmicpc.net/problem/12996 12996번: Acka 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S) www.acmicpc.net [풀이] DP의 메모이제이션으로 풀어야 하는 문제였다. 3명을 a,b,c라고 했을 때 곡을 부르는 경우는 (a),(b),(c),(a,b),(a,c),(b,c),(a,b,c) 이렇게 7가지가 있으므로 각 곡마다 중복을 제거하면서 더해주면 된다. DP[s][x][y][z] : 곡이 s개 남고 a가 x곡, b가 y곡, c가 z곡 남았을 때의 경우의 수 #include #include //mem..
www.acmicpc.net/problem/12026 12026번: BOJ 거리 스타트가 링크를 만나는데 필요한 에너지 양의 최솟값을 출력한다. 만약, 스타트가 링크를 만날 수 없는 경우에는 -1을 출력한다. www.acmicpc.net [풀이] DP를 이용하여 풀 수 있는 문제였다. DP[i] : i번째 칸까지 가는데에 필요한 에너지 양의 최솟값 점화식 DP[j] = min(DP[j], (j-i)*(j-i)+DP[i]) #include #include //min, fill using namespace std; int N; char street[1001]; int DP[1001]; void solution() { DP[1] = 0; for (int i = 1; i < N; i++) { if (street..
www.acmicpc.net/problem/14238 14238번: 출근 기록 스타트링크에는 세명의 직원이 일을 하고 있다. 세 직원의 이름은 강호(A), 준규(B), 수빈(C) 이다. 이 회사의 직원은 특별한 룰을 가지고 있는데, 바로 하루에 한 명만 출근한다는 것이다. 3일간의 www.acmicpc.net [풀이] 재귀 DP를 이용하여 풀 수 있는 문제였다. (bool) DP[a][b][c][pp][p] : A가 기록을 a번, B는 b번, C는 c번 했고 전전날 pp가 기록을 했고 전날 p가 기록을 한 경우가 가능한지 #include #include using namespace std; int worker[3];//0:A, 1:B, 2:C 입력받은 횟수 저장 bool DP[51][51][51][3][..
www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀�� www.acmicpc.net [풀이] DP로 풀 수 있는 문제였다. DP[i][j] : i번째 숫자차례에서 덧셈 혹은 뺄셈한 결과가 j인 경우의 수 점화식 DP[i][j+Num[i]] += DP[i-1][j] DP[i][j-Num[i]] += DP[i-1][j] #include using namespace std; int N; int Num[101]; long long DP[101][21] = { 0, }; void soluti..