EQ1의 짱무말 갓잔치 EQ1의 짱무말 갓잔치

알고리즘 자체가 어려운 문제는 아니었는데 깔끔하게 예외처리를 하는데 시간을 더 많이 쏟았다. 하나하나 다 막아주다가 사고방식을 바꿔서 그래도 나름 깔끔하게 예외 처리해서 만족. 풀이 코드를 여러 방법으로 해석하기 위해서는 붙어 있는 두 숫자가 1에서 26 사이여야 한다. 그 외의 경우는 반드시 한 가지로만 해석 할 수 있거나 해석할 수 없는 잘못된 코드이다. 먼저 dp를 정의해보자. dp [i] : 0번째부터 i-1번째까지만 코드가 있을 때 해석 가능한 경우의 수 따라서 i-2번째와 i-1번째 수를 두 자릿수로 봤을 때 10 이상 26 이하면 i-1번째 수를 단독으로 해석할 수도 있고 두자리수로 해석할 수 있다. 10 이상 26 이하 : dp [i] = dp [i-1] + dp [i-2] 26 이상 : ..

쉬운 문제인데 한 번 틀려서 괜히 자존심 상한다... 출력 값의 범위가 int를 벗어나서 생기는 문제여서 int로 선언한 dp 배열을 long long으로만 바꿔서 제출했더니 맞았다.ㅠㅠ 풀이 흔한 dp 문제다. 오른쪽 또는 아래쪽으로만 갈 수 있으므로 dp 계산을 위해 이중 for문 한 번만 사용하면 된다. 심지어 내가 쓴 코드에서 입력을 읽음과 동시에 바로 dp를 계산하면 아주 짧게 끝날 수도 있다. dp [i][j] : i열 j행까지 도착할 수 있는 경우의 수 시작은 항상 1열 1행이고 오른쪽, 아래쪽으로만 갈 수 있으므로 다시 되돌아가는 경우는 절대로 발생할 수 없다. 따라서 자신의 위치에 도달할 수 있고 dp[i][j] != 0 자신의 값이 종착점이 아니면 value[i][j] != 0 자신의 ..

와우... 이걸 푸는 다른 정석적인 풀이가 있을 것이지만... 나는 좀ㅋㅋㅋㅋ 편법적으로 풀었다. 만약 정석적인 풀이를 원하신다면 다른 블로그들을 참고하시길 바랍니다....ㅋㅋ 풀이 평범한 냅색문제처럼 접근했다. 일단 사용할 추의 무게들을 이용해 미리 만들 수 있는 무게를 저장해둔다. 만들 수 있는 무게를 계산하는 방법은 무게를 확인할 구슬이 양팔저울의 왼쪽에 있다고 가정했을 때 추를 오른쪽에 두면 그 만큼의 무게를 더하는 것이고 추를 왼쪽에 두면 그 만큼의 무게를 빼는 것이다. 그렇다면 dp를 다음과 같이 정의할 수 있다. dp[i][j] : i번째 추까지 사용했을 때 j라는 무게를 측정할 수 있는지 없는지 만약 추를 구슬의 반대쪽에만 둔다고 하면 무게를 계속 더하기만 하면 될 것이다. 그래서 1g과 ..

'뭐야? 이 문제 쉽잖아? 살짝 변형하면 어디서 본 것 같은데?'라고 생각했다가 '시간 초과'나고 '틀렸습니다' 뜨고... ㅎㅎ 왜 항상 어디서 본 것 같은데 틀리는 것일까... 흠... 풀이 처음에 dp를 정할 때 조금 헷갈렸다. 보통 변하는 값 2개를 dp의 한 축으로 두는 경우가 많아서 '소형 기관차의 개수는 3개로 고정이니까 그거 말고 다른 것을 dp의 축으로 둬야지 ^^!'라고 생각한 게 오판이었다. dp [i][j] : 소형 기관차가 i개 있고 객실이 j번까지 있을 때 운송가능한 최대 승객 수 그 외의 변수를 정의하고 가면 n : 총 객실 수 m : 소형기관차가 끌 수 있는 최대 객실 수 sum [k] : 1번 객실부터 k번 객실까지 승객의 총합 소형 기관차가 i-1개였다가 1개 추가되서 i개..

처음 이 문제를 보고 단순히 가까운 것을 swap 하기만 하면 되는 줄 알고 'dp 쓸 필요도 없겠네~!'라고 좋아하면서 덤볐다가 코드를 짜면서 좀 더 생각해보니까 가까운 것만 swap하는 것이 최소가 아니라는 것을 깨닫고.... 이진트리를 이룬다는 사실을 깨닫고... ㅠㅠ 나의 멍청스러움에 슬퍼하면서 얌전히 dp를 사용했다. 풀이 dp[index][open1][open2] open1과 open2번째의 벽장이 열려있을 때 index 단계의 벽장을 열기 위한 최소 이동횟수 'index 단계의 벽장을 연다'라는 말이 모호해서 추가설명을 하자면 문제의 예시에 3, 1, 6, 5번 벽장을 순서대로 이용하려고 한다고 되어있다. 이때 index=2라는 것은 '두번째 단계의 벽장을 이용한다', 즉 1번 벽장을 이용하..

혼자 생각해서 풀었더니 시간에 야무지게 초과해버려서 슬퍼하면서 검색을 했다. 와 역시 검색이 짱이야... 검색해서 나온 코드를 보고 내 방식대로 더 깔끔하게 수정해서 제출했다. 내가 참고한 블로그는 4ms였는데 나는 0ms 나왔으니까 내가 더 깔끔함! 암튼 그럼! 풀이 n개의 숫자가 주어졌을 때 적당히 그룹을 짓고 그룹 내에서 최대 최소의 차를 구한 것이 그룹의 점수이며 그룹 점수를 모두 더한 것이 dp의 정의다. dp[n] : n번째 숫자까지 최대 그룹 합 마지막 숫자인 n번째 숫자가 포함된 그룹의 첫 번째 숫자가 전체 수열 중 j번째 숫자라고 하자. 이때 j는 최대 n이고 최소 1이다. 이때 dp [n]은 다음과 같이 계산할 수 있다. dp [n] = 그룹 점수 + dp [j-1] 그룹은 j번째 수부..

험멈멈... 왜 어렵지....? 어려울 것 같은 문제가 아니었는데 어렵다! 이럴 수가... 난 바보인가바... 풀이 dp를 잘 정의해보자. dp[n][m] : 첫 번째부터 n번째까지의 수들 중에서 m개의 구간을 선택했을 때 구간 합의 최댓값 n번째까지의 수 중에서 n번째 숫자가 구간에 포함되지 않았을 경우 이 경우 n번째 숫자가 없는 것과 마찬가지다. dp [n][m] = dp [n-1][m] n번째까지의 수 중에서 n번째 숫자가 구간에 포함되었을 경우 이 경우 n번째 숫자는 마지막 구간, 즉 m번째 구간에 포함되었을 것이다. m번째 구간이 k번째 수부터 n번째 수까지라고 가정해보자. m-1번째 구간은 m번째 구간과 인접할 수 없으므로 k-1번째 수는 사용할 수 없다. 따라서 k-2번째 수까지만 사용해서..

흔히 보던 타일 문제여서 쉬운 이겠거니 하고 덤볐다가 의외로 어려워서 쩔쩔맸던 문제... dp만 주구장창 풀어도 아직도 어렵다. 이 문제는 좌우 대칭이 아닌 경우를 세는 문제로 보이지만 역설적이게도 좌우 대칭인 경우를 세야한다. 글로 써놓고 보니까 단순히 여집합의 관계니까 그 정도 발상은 쉬운 거 아니냐 싶겠지만 나도 그렇고 이 문제로 검색을 해보면 많은 사람들이 이 발상이 어려웠다고 한다. 발상의 전환을 잘 기억해두도록 하자. 풀이 dp의 정의는 이런 타일 방식의 문제에 자주 쓰던 그 방식이다. dp[n] : 길이가 n인 판(2 ×n)을 주어진 타일(1×2, 2×1, 2×2)로 채울 수 있는 경우의 수 dp는 대칭을 고려하지 않고 일반적이게 잡는다. dp를 구하는 방법 이 dp를 구하는 점화식은 어렵지..