안 쓰던 블로그

www.acmicpc.net/problem/2133 dp[n] = 3xn 직사각형 채우는 방법의 수 1. n이 홀수면 채울 수 없다 2. n=2면 3가지 방법이 있다 3. n=4면 3x2만큼은 dp[2]에서 했던 값을 사용, 나머지 3x2에 대한 방법이 또 3가지 있다 dp[2]에서 했던 부분을 왼쪽을 잡든 오른쪽을 잡든 같으니까 같은 수로 친다 dp[2]x3=9만큼의 경우의 수가 나온다 그리고 특수 케이스가 있다 이렇게 엇갈리는 방법 두 가지가 있다 dp[4]=dp[2]*3+dp[0]*2 가 된다. dp[4]=11 3. n=6이면 dp[2]+dp[4] 이렇게 볼 수 있지만 둘은 중복되는 모양이 너무 많다 그래서 일단 dp[2]*dp[4]를 해 놓고, 중복 없이 나머지를 넣어야 한다 dp[2]*dp[4]..

www.acmicpc.net/problem/2294 dp배열은 합이 j일 때의 최소 동전 개수를 나타낸다 현재 금액만 사용했을 때 최소 몇 개의 동전이 필요한가 하나씩 보며 전체 dp배열을 업데이트하는 식이다 1원 쓸 때는 1~15원까지 각 개수만큼 사용해서 1,2,3..15까지가 배열에 들어간다 다음 5원 쓸 때는 1~4원까지는 1원을 쓴 그대로 두고, 5원은 5원 1개로 만들 수 있으니까 1이 되고, 6,7,8,9까지는 5+x개의 1원을 쓰니까 각각 2,3,4,5개를 사용해서 만들 수 있다 이 때 이전에 1원 기준으로 계산했던 값에서+5원을 하면 (5원 1개+1원 x개)로 만든 값이 나오니까 j-a[i](1원 x로 만든 값)+1(5원 1개 더한 값)이 식이다. j-a[i]+1 이 값을 현재까지의 최소..

www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net #include #include #include #include using namespace std; int dp[101][11]; //i자리 숫자면서 j로 시작하는 계단 수 -> 틀림 //이거 남들은 j로 끝나면~으로 하던데 시작해도 딱 떨어지는 것 같음(아마..일단 내가 계산한 만큼은) -> 이거 틀림 //다만 10으로 시작하는 건 1개씩 늘어나고 12로 시작하는 건 2개씩 늘어나니까 [1][0]은 10~, [1][1]은 12~로 나눠줌 ->틀림 //---------- //i자리 숫자면서 j로 끝나는 계단 수로 해야 계산..

입력 4 6 101111 101010 101011 111011 입력 코드 cin >> n >> m; for (int i = 0; i > a; for (int j = 0; j < m; j++) { map[i][j] = a[j] - '0'; } }

관련 문제 -이진 검색 트리: www.acmicpc.net/problem/5639 (전위->이진트리) -완전 이진 트리: www.acmicpc.net/problem/9934 (중위->이진트리) 이진 검색 트리 문제부터 본다 전위 순회한 결과 값으로 후위 순회하는 문제이다 전위 순회는 루트-왼쪽-오른쪽 순으로 방문한다 이진 트리는 들어온 값을 루트부터 시작하여 값이 큰지 작은지 비교, 왼쪽/오른쪽 어느 서브 트리로 보낼지를 결정해야 한다 이 문제에서 전위 순회 결과로 이진트리를 만드는 작업은 다음과 같이했다(참고: www.acmicpc.net/problem/1539 ) 1. 전위 순회는 무조건 첫 값이 루트이므로 첫 값은 루트로 넣는다 2. 값을 하나 입력 받는다 3. 현재 노드를 나타낼 now변수를 둔다..

6068 시간 관리하기 1263 시간 관리 '늦잠을 언제까지 잘 수 있냐'가 문제이기 때문에 끝나는 시간을 기준으로 내림차순 정렬하고 앞에서부터(가장 끝나는 시간이 늦은 일부터) 일을 최소 언제부터 시작해야 하는지를 계산한다 예제로 보면, 5 20은 최소 15에는 시작해야 한다 1 16은 최소 15에는 시작해야 하지만, 15에는 5 20이 해야 하므로 앞으로 밀려서 14에는 시작해야 한다 8 14는 최소 6에는 시작하면 된다 3 5는 최소 2에 시작하면 된다 github.com/proqk/Algorithm/blob/master/greedy/6068%20%EC%8B%9C%EA%B0%84%20%EA%B4%80%EB%A6%AC%ED%95%98%EA%B8%B0(1263%20%EC%8B%9C%EA%B0%84%20..

4796 캠핑 단순한 생각- 예를 들어 8일 중에 5일을 사용할 수 있으며 총 휴가가 20일이면 8일(5일)-8일(5일)-4일=14일을 캠핑할 수 있다 계산 방법 그대로 휴가를 일 수로 나누고 나머지를 더하면 된다 근데 여기서 함정은, 남은 일수가 연속 일수보다 큰 경우다 위에서는 8일 중에 5일을 사용할 수 있는데 남은 일수가 4일이라서 그냥 넣으면 됐다 근데 만약 남은 일수가 6일이라면? 최대 5일밖에 사용할 수 없다 이 두 가지 경우를 주의해 주면 되었다 github.com/proqk/Algorithm/blob/master/greedy/4796%20%EC%BA%A0%ED%95%91.cpp 2891 카약과 강풍 각 팀이 가지고 있는 카약의 수를 인덱스로 만들어서 더하거나 빼면 되었다 처음엔 모든 팀이..