본문 바로가기

분류 전체보기

 (96)
[C++] 백준 9252: LCS 2 https://www.acmicpc.net/problem/9252  LCS 1에서 발전한 문제이다!https://dmoritle.tistory.com/entry/%EB%B0%B1%EC%A4%80-9251-LCS [C++] 백준 9251: LCShttps://www.acmicpc.net/problem/9251 모든 가능한 수열을 다 비교할경우 0.1초의 시간제한으로 인해 틀리게된다.이 문제의 경우 DP를 사용하면 편하게 풀 수 있다!  자, DP이므로 배열의 의미를 잘 지정하dmoritle.tistory.com안 풀어본 분들께서는 위의 포스팅을 참고해주시면 좋을 것 같다!  풀이LCS 1과의 차이점은 LCS인 문자열을 출력해줘야 한다는 것이다.dp배열을 다 구해둔 상태이니 역추적을 하면 될 것 같다.  f..
[C++] 백준 14002: 가장 긴 증가하는 부분 수열 4 https://www.acmicpc.net/problem/14002  가장 긴 증가하는 부분 수열을 선행했다면 굉장히 쉽게 풀 수 있는 문제였습니다. 풀이int n; cin>>n; for(int i = 1; i >num[i]; dp[i] = 1; } for(int i = 2; i num[j]) dp[i]++; } }먼저 위와 같이dp[i] = i번째 숫자가 끝일 때, 가장 긴 증가하는 부분 수열의 길이로 설정하고,그 값을 구해줍니다.  한 개의 원소로 구성된 수열은 값이 1이기에 초깃값으로 설정해주고,원소의 범위를 늘려가며 가장 긴 증가하는 부분 수열의 길이를 구해줍니다.  조건문의 조건에 대해 살펴보겠습니다.먼저, 증가하는 부분 수열이기에 num[i..
[C++] 백준 2096: 내려가기 https://www.acmicpc.net/problem/2096 왼쪽으로 내려갈 때,가운데로 내려갈 때,오른쪽으로 내려갈 때 3가지의 경우의 수에 대하여 각각의 점화식을 세우면 쉽게 풀 수 있다고 생각되는 문제였습니다. 풀이dp[i][j][k] = i번째 행의 j번째 자리일 때 얻을 수 있는 최댓값 or 최솟값(k로 구분, 0은 최댓값 1은 최솟값)  왼쪽으로 내려갈 수 있는 건,이전 단계에서 왼쪽에 있을 때와 가운데에 있을 때입니다.dp[i][0][k] = dp[i-1][0][k] + dp[i-1][1][k] 가운데로 내려갈 수 있는 건,이전 단계에서 왼쪽, 가운데, 오른쪽입니다.dp[i][1][k] = dp[i-1][0][k] + dp[i-1][1][k] + dp[i-1][2][k] 오른쪽으로 내려..
[C++] 백준 17070: 파이프 옮기기 1 https://www.acmicpc.net/problem/17070 dp배열의 값 설정문제에서 (N,N)로 이동시키는 방법의 개수를 물어봤으므로, dp[i][j] = (i, j)까지 이동시키는 방법의 개수라고 가정하고 시작했다. 이 문제는 좌표뿐만 아니라 방향값도 존재하므로 배열의 차원을 하나 늘려방향값도 저장하는 게 좋겠다는 생각이 들었다. 그래서 dp[i][j][k] = k의 방향을 가지는 (i,j)까지 이동시키는 방법의 개수로 가정했다.   처음에 파이프는 가로 방향으로 (1,2)에 끝이 위치하므로 dp[1][2][0] = 1; 다음과 같이 초기값을 설정했고,그 후에 점화식을 생각해보았다.   점화식 구하기dp[n][n][0] = 가로 방향으로 (n,n)까지 이동시키는 방법의 개수이다. 즉, ..
[C++] 백준 1005: ACM Craft 문제 이해건물은 짓는 순서는 매 게임마다 주어진다.각 건물에는 건설 시간이 존재한다.건설은 동시에 진행이 가능하고, 건물 순서상 필요한 건물이 모두 건설되었을 때 다음 건물을 건설할 수 있다.특정 건물을 가장 빨리 건설할 때까지 걸리는 최소 시간을 구하여라.T: 테스트 케이스N: 건물의 개수 1 ~ 10^3K: 건물순서 규칙의 총 개수 1 ~ 10^5Di: 각 건물 건설에 걸리는 시간 1 ~ 10^5{X, Y}: 건설 순서W: 백준이가 승리하기 위해 건설해야 하는 건물의 번호  풀이특정 건물을 짓는데 걸리는 최소시간을 구하는 문제이다. 각 건물마다 짓는데 걸리는 최소시간을 DP로 저장해놓고,순서가 주어진 그래프를 위상정렬을 하면 되는 문제이다.즉, DP와 위상정렬에 대해 둘 다 알고있어야 풀 수 있는 문..
[C++] 백준 2565: 전깃줄 https://www.acmicpc.net/problem/2565 풀이입력을 받을 때 두 개의 전깃줄을 동시에 받으므로 vector 자료형의 pair를 통해 받은 뒤,정렬을 해주면 될 것 같았다.  정렬을 하고 ,dp[i] = i번째 전깃줄이 교차하지 않고 연결되어 있기위한 없애야 하는 전깃줄의 최소 개수로 가정하고 풀이를 떠올려봤는데 도저히 감이 안 잡혔다.  인터넷 검색을 통해 풀이를 슬쩍 봤는데,가장 긴 증가하는 부분수열을 활용하는 문제라고 나와있었다.그걸 보자마자 무릎을 탁 쳤다!!https://www.acmicpc.net/problem/11053  dp[i] = i번째까지 중 가장 긴 증가하는 부분수열의 길이로 하면이미 좌측 배열의 값은 정렬이 되어있는 상태이기에, dp[i] = i번째까지의 전..
[C++] 백준 2133: 타일 채우기 https://www.acmicpc.net/problem/2133 문제의 설명이 매우 단순하니만큼 시뮬레이션을 돌려봐야 할 거 같다는 생각이 들었다.dp[i] = 3 * i 크기의 벽을 타일로 채우는 경우의 수로 가정하고, 차근차근 N = 1부터 진행해보자. 풀이N = 12 * 1과 1 * 2의 타일로는 3 * 1을 채울 수 없다.즉 dp[1] = 0  N = 2 로 총 3가지의 모양이 나온다.즉 dp[2] = 3  N = 3역시 타일을 채울 수 없었다.여기까지 했으면 N에 홀수가 들어갈경우 dp배열의 값이 0이라는 걸 추측이 가능하다.  N = 4중앙을 기준으로 나눴을 때, dp[2] * dp[2] = 9라는 걸 알 수 있다.그럼 dp[4] = 9인걸까??? 답은 아니다이다.문제의 힌트를 유심히 보면4..
[C++] 백준 2225: 합분해 https://www.acmicpc.net/problem/2225 합이 N이 될 수 있는 경우의 수를 구하는 문제이다! 이 문제를 어렵게 하는 건 다음의 사항이었다.1. 0도 더할 수 있다.2. 한 개의 수를 여러 번 쓸 수 있다.   풀이일단 dp를 사용하면 될 것 같았다.1차원 dp를 n에 따라 사용해볼까 했지만,k라는 변수도 사용하려면 2차원 배열을 사용해야 될 것 같았다. 그래서 dp[i][j] = i개의 숫자를 사용해서 j가 되게 하는 경우의 수로 가정했다.  수학 아이디어가 좋아 점화식이 파바박 나오면 좋겠지만 그렇지는 않았다.그렇기에 일단 시뮬레이션을 돌려보기로 했다.N = 4, K = 4로 하고 시뮬레이션을 돌려봤다. K\N12341111122345336101544102035 무언가 규칙이..

티스토리툴바