목록백준 (183)
Study hard
www.acmicpc.net/problem/16637 16637번: 괄호 추가하기 첫째 줄에 수식의 길이 N(1 ≤ N ≤ 19)가 주어진다. 둘째 줄에는 수식이 주어진다. 수식에 포함된 정수는 모두 0보다 크거나 같고, 9보다 작거나 같다. 문자열은 정수로 시작하고, 연산자와 정수가 www.acmicpc.net [풀이] dfs를 이용하여 풀 수 있는 문제였다. 괄호를 묶을 수 있는지 확인하는 것이 필요하다. 1. 괄호 묶을 수 있는지 확인(남은 개수 확인) 2. 현재까지 계산한 값과 다음 값 사이의 연산자 저장 3. 괄호를 묶는 경우. 괄호 묶은 연산자 계산하고 이전까지의 값과 계산 4. 괄호를 묶지 않는 경우. 현재 위치의 값과 이전까지의 값 계산 ※Max값 초기화할 때 습관적으로 -1 했다가 "틀렸..
www.acmicpc.net/problem/15591 15591번: MooTube (Silver) 농부 존은 1번 동영상과 2번 동영상이 USADO 3을 가지고, 2번 동영상과 3번 동영상이 USADO 2를 가지고, 2번 동영상과 4번 동영상이 USADO 4를 가진다고 했다. 이것에 기반해서 1번 동영상과 3번 동영상의 www.acmicpc.net [풀이] bfs를 사용하여 USADO가 k이상인 비디오의 개수를 세 주었다. ※query마다 visited배열을 false로 초기화해야한다. #include #include #include using namespace std; struct Video { int v; int USADO; }; int N, Q; int p, q, r; vectorMoo[5001];..
www.acmicpc.net/problem/2163 2163번: 초콜릿 자르기 정화는 N×M 크기의 초콜릿을 하나 가지고 있다. 초콜릿은 금이 가 있는 모양을 하고 있으며, 그 금에 의해 N×M개의 조각으로 나눠질 수 있다. 초콜릿의 크기가 너무 크다고 생각한 그녀는 초콜릿� www.acmicpc.net [풀이] DP로 풀 수 있다. 먼저 세로로 N번 자르고 각각 조각마다 M번씩 자른다. 점화식 DP[i] = DP[i-1] + N #include using namespace std; int N, M; int DP[301]; void solution() { DP[0] = N - 1;//처음에 세로로 N-1번 자름 for (int i = 1; i < M; i++) DP[i] = DP[i - 1] + N;//..
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..