호지

처음에 DFS로 풀었으나 시간초과로 틀렸다. DP문제는 해도해도 헷갈린다ㅜ dp[n][i][j]는 n번째 움직임에서 왼쪽발이 i에 있고, 오른쪽이 j에 있을때 power의 최솟값을 뜻한다. 1번째 움직임에서 가능한 경우는 왼발이 moves[1]에 있거나 오른발이 moves[1]에 있을 때이다. 따라서 dp의 초기값은 dp[1][moves[1]][0] = 2, dp[1][0][moves[1]] = 2이다. (0에서 이동한 경우엔 power가 2) 2~n까지 탐색을 통해 dp값을 채우면 dp[n]의 최솟값이 구하고자하는 power의 최솟값이다. 양발은 같은 위치에 있으면 안 되므로 if(moves[x] !=i) , if(moves[x] !=j)로 확인한다. x1-> x2의 이동의 power계산은 scores..

1766번 문제집 풀이가 비슷하다 https://hoji25.tistory.com/27 [백준 알고리즘] 1766번 문제집 문제풀이 c++ 1~n개의 문제 중 앞 번호의 문제를 먼저 푸는게 더 좋다. m개의 선행되어야할 문제 조건이 주어지는데 이 조건을 만족하면서 앞 번호의 문제를 우선적으로 풀 때 결과를 출력하면 된다. 위상정렬 hoji25.tistory.com order 벡터에는 자기보다 키가 큰 학생의 번호를 저장한다. ex) 3번학생보다 4번, 5번 학생이 키가 크다면 order[3]벡터에는 4,5가 저장되어있다. cnt배열에는 자기보다 키가 작은 학생의 수가 저장되어있다. 자기보다 키가 작은 학생이 0명이면 바로 줄을 설 수 있으므로 queue에 push한다. queue가 empty일때까지 wh..

pos에 부분합의 가장 왼쪽 위치, len에는 부분합의 길이, sum에는 부분합의 합계를 저장한다. 0~n까지 i for문을 돌면서 len을 1증가하고 list[i]를 sum에 더한다. 이 때, sum이 s이상이라면 sum이 s보다 작을 때까지 while문을 돌면서 부분합의 최소 길이를 구한다. #include using namespace std; int list[100000]; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int n; long long s; cin >> n >> s; for(int i=0; i> list[i]; } int pos = 0, len = 0, res = 100001; long lon..

dp와 비트마스크를 활용한 문제. 배열 dp[x][y][z]에서 x는 계단수의 길이, y는 0~9인 숫자, z는 비트마스크로 사용된 숫자를 체크한다. 길이가 1이면서 숫자 1~9가 사용되었을 때 dp를 채운다 (0으로 시작하는 수는 계단수가 아니므로 0은 제외) 길이가 2~n일때(len for문) 숫자 0~9에 대해(num for문) 비트마스크 0000000000~1111111111일 때(i for문) dp값을 채운다. i for문에서 해당 비트마스크를 순차탐색하여 dp를 채울 수 있는 이유는 길이가 1일때, dp[1][1][2], dp[1][2][4], dp[1][3][8]...이 1이고, 길이가 2일때, dp[2][0][3], dp[2][1][6], dp[2][2][1], dp[2][2][12].....