n개의 정수로 이루어진 수열A가 주어지고
1 <= p <= q <= r <= s <=n 인 p, q, r, s에 대하여
A[q] < A[s] < A[p] < A[r] 또는 A[q] > A[s] > A[p] > A[r]을 만족하는 경우가 있다면 Yes를 출력하고 아니라면 No를 출력하는 문제이다.
2016년 9월 30일 금요일
BOJ 2266 금고 테스트
N층짜리 빌딩이 있다. F층은 금고가 부서지는 최소 층이다. 즉 F층 이상의 층에서 금고를 떨어뜨리면 금고는 부서지고 F층 아래에서는 떨어뜨려도 부서지지 않는다. F층을 알아내기 위해 금고 k개를 가지고 떨어뜨려 보려고 하는데, 금고가 부서지면 다시 사용할 수 없다. F층이 몇층이든 간에 N층짜리 빌딩에서 k개의 금고를 이용해 F층을 알아낼 수 있는 금고의 낙하 횟수의 최소값을 구하는 문제이다.
구하라고 하는 것이 잘 와닿지가 않는다. 어렵다.
금고가 1개일 경우, 그 금고가 F층을 찾기 전에 깨지면 더 이상 F층을 알 방법이 없으므로 이 경우에는 1층부터 한 층씩 올라가면서 테스트를 해봐야 해서 금고의 낙하 횟수의 최소값은 N이 된다. 이 예에서 알 수 있듯이 우리가 구하고자 하는 것은 F가 몇층이든 간에 N층자리 빌딩에서 k개의 금고를 이용해 F층을 알아낼 수 있는 금고의 낙하 횟수의 최소값이다. 여기서 최소값이긴 한데 (F가 몇 층이든 간에)라는 조건이 있기 때문에, 결국 F가 1층부터 N층일 수 있는 것이고 F가 1부터 N 층일 때의 각각에 대한 최소값을 구해서 그 중 최악의 경우(최대값, F가 몇 층이든 간에 라는 조건이 있으므로!)을 구해야 하는 문제이다.
그럼 F를 1층, 2층, ...N층이라 가정하고 k개의 금고를 최소 몇 번 떨어뜨려야 F를 알아낼 수 있는지 구해보면 될 것이다.
어떻게 할까? 쉽게 생각할 수 있는 것은 만약 금고를 떨어뜨려 보다가 금고가 하나가 남는다면 한 층 한 층 아래서부터 차례로 봐야할 것이다. 그러면 금고가 하나 남기 전까지는 뭘 해야할까? 바로 F층이 존재하는 범위가 처음에는 1~N이었다면, 금고를 1~N중간에 떨어뜨려서 범위를 반으로 줄일 수 있을 것이다(이분 탐색처럼) 이렇게 하나가 남을 때까지 범위를 줄이고 하나가 남으면 최종적으로 줄여진 범위내에서 가장 아래부터 하나씩 보는 것이다.
이분 탐색을 할 때 주의할 점이 안 깨지는 경우 재활용 가능하다는 것과, mid에서 깨지는 경우 r=mid-1로 아래층으로 하는 게 아니라 자기 자신(mid)도 F층일 가능성이 있으므로 r=mid로 해줘야 한다. 그리고 l==r이 되면 이분 탐색만으로 F층을 구한 것이 된다.
WA를 받았다. 질문 게시판을 봤는데, portableangel님의 멋진 답변이 있었다.
왜 이분탐색으로 풀면 안 되는지를 직접 예를 들어 설명해 주셨다.
그리고 이분 탐색으로 구현하면서 최악의 경우를 구하는 것이었다면 나처럼 복잡하게 할 필요 없는 것 같다... 좀 완전히 잘못 생각한 것 같다.
백준님이 dp로 설명해 주셨는데, dp를 조금 고민해보다가 풀이를 봐야겠다.
portableangel님의 답변에 기반하여 생각해 보면 꼭 가운데 층에서 떨어뜨리는 게 좋은 것은 아니기 때문에 1층부터 n층까지 다 떨어뜨려 보는 경우를 해봐야할 것 같다.
d[n][k] = n층에서 k개의 금고를 가지고 F층을 알아낼 수 있는 최소의 금고 낙하 횟수
d[n][k] = MIN(s층에서 시작, MAX(깨진 경우:d[s-1][k-1], 깨지지 않은 경우:d[n-s][k]) )
떨어뜨리는 것을 모든 층에서 다 해봐야하고 그 중 최대(최악)의 경우를 구해서 그것들 중 최소를 구하면 될 것이다.
여기서 깨진 경우 d[s-1][k-1]에서 좀 헷갈렸는데, s에서 깨졌다면 s개가 아니라 s-1개만 보면 되는 이유는 s번째는 이미 봤고 깨졌다는 걸 알기 때문에 s-1개를 본 결과에 따라 s번째를 판단할 수 있기 때문이다.**
와 AC를 받았다... 백준님의 설명을 저번 주에 듣긴했지만 기억이 안났었는데, 나도 모르게 기억하고 있었던 건가... portableangel님의 설명이 많이 도움이 됐다.
그리고 시간이 많이 나와서 다른 분들 코드를 보는데, sys7961님의 코드가 나랑 비슷한데, 시간은 많이 차이가 나서 자세히 보니 나는 dp(n, k)를 호출한 반면에,
sys7961님은 dp(n, min(9, k))를 호출하셨다. 아까 이분탐색으로 짰던 코드에서 n을 500으로 하고 해보면 보통 9가 나오던데 아마 500층 이내에서는 9개가 넘는 금고는 불필요한 것 같아보인다. 9개의 금고로도 커버가 되는 것 같다. sys7961님도 대단하신 것 같다. 난 아까 9가 나오는 걸보고도 생각도 못했는데...
이 문제는 예전에 면접이나 코딩 테스트에서도 자주 나왔던 문제라고 하고 유명하다고 한다. 수학적으로 접근하는 방법도 있고.. 그리고 좀 푸는데 애먹었으니 나중에 꼭 다시 혼자 힘으로 풀어보도록 하자.
구하라고 하는 것이 잘 와닿지가 않는다. 어렵다.
금고가 1개일 경우, 그 금고가 F층을 찾기 전에 깨지면 더 이상 F층을 알 방법이 없으므로 이 경우에는 1층부터 한 층씩 올라가면서 테스트를 해봐야 해서 금고의 낙하 횟수의 최소값은 N이 된다. 이 예에서 알 수 있듯이 우리가 구하고자 하는 것은 F가 몇층이든 간에 N층자리 빌딩에서 k개의 금고를 이용해 F층을 알아낼 수 있는 금고의 낙하 횟수의 최소값이다. 여기서 최소값이긴 한데 (F가 몇 층이든 간에)라는 조건이 있기 때문에, 결국 F가 1층부터 N층일 수 있는 것이고 F가 1부터 N 층일 때의 각각에 대한 최소값을 구해서 그 중 최악의 경우(최대값, F가 몇 층이든 간에 라는 조건이 있으므로!)을 구해야 하는 문제이다.
그럼 F를 1층, 2층, ...N층이라 가정하고 k개의 금고를 최소 몇 번 떨어뜨려야 F를 알아낼 수 있는지 구해보면 될 것이다.
WA를 받았다. 질문 게시판을 봤는데, portableangel님의 멋진 답변이 있었다.
왜 이분탐색으로 풀면 안 되는지를 직접 예를 들어 설명해 주셨다.
그리고 이분 탐색으로 구현하면서 최악의 경우를 구하는 것이었다면 나처럼 복잡하게 할 필요 없는 것 같다... 좀 완전히 잘못 생각한 것 같다.
백준님이 dp로 설명해 주셨는데, dp를 조금 고민해보다가 풀이를 봐야겠다.
portableangel님의 답변에 기반하여 생각해 보면 꼭 가운데 층에서 떨어뜨리는 게 좋은 것은 아니기 때문에 1층부터 n층까지 다 떨어뜨려 보는 경우를 해봐야할 것 같다.
d[n][k] = n층에서 k개의 금고를 가지고 F층을 알아낼 수 있는 최소의 금고 낙하 횟수
d[n][k] = MIN(s층에서 시작, MAX(깨진 경우:d[s-1][k-1], 깨지지 않은 경우:d[n-s][k]) )
떨어뜨리는 것을 모든 층에서 다 해봐야하고 그 중 최대(최악)의 경우를 구해서 그것들 중 최소를 구하면 될 것이다.
여기서 깨진 경우 d[s-1][k-1]에서 좀 헷갈렸는데, s에서 깨졌다면 s개가 아니라 s-1개만 보면 되는 이유는 s번째는 이미 봤고 깨졌다는 걸 알기 때문에 s-1개를 본 결과에 따라 s번째를 판단할 수 있기 때문이다.**
와 AC를 받았다... 백준님의 설명을 저번 주에 듣긴했지만 기억이 안났었는데, 나도 모르게 기억하고 있었던 건가... portableangel님의 설명이 많이 도움이 됐다.
그리고 시간이 많이 나와서 다른 분들 코드를 보는데, sys7961님의 코드가 나랑 비슷한데, 시간은 많이 차이가 나서 자세히 보니 나는 dp(n, k)를 호출한 반면에,
sys7961님은 dp(n, min(9, k))를 호출하셨다. 아까 이분탐색으로 짰던 코드에서 n을 500으로 하고 해보면 보통 9가 나오던데 아마 500층 이내에서는 9개가 넘는 금고는 불필요한 것 같아보인다. 9개의 금고로도 커버가 되는 것 같다. sys7961님도 대단하신 것 같다. 난 아까 9가 나오는 걸보고도 생각도 못했는데...
이 문제는 예전에 면접이나 코딩 테스트에서도 자주 나왔던 문제라고 하고 유명하다고 한다. 수학적으로 접근하는 방법도 있고.. 그리고 좀 푸는데 애먹었으니 나중에 꼭 다시 혼자 힘으로 풀어보도록 하자.
BOJ 10571 다이아몬드
이 문제는 smart elephant문제와 비슷한 문제(거의 똑같을지도..)이다.
다이아몬드의 중량과 선명도가 주어지면 중량이 늘어나고, 선명도가 줄어들게 다이아몬드를 나열했을 때 최대 길이를 구하는 문제이다.
풀이는 중량 기준으로 오름차순으로 정렬한 목록에서 선명도의 가장 긴 줄어드는 부분 수열의 길이를 구하면 된다. (반대로 선명도 기준으로 내림차순으로 정렬하고 중량의 LIS를 구해도 된다... LIS가 좀 더 익숙하니 이게 더 나을 수도...)
하나 주의할 점은 중량 기준으로 오름차순으로 정렬할 때, 만약 중량이 같다면 선명도가 내림차순 기준으로 정렬되도록 해줘야 할 것이고, 또한 smart elephant에서는 중량이 같고 선명도가 줄어드는 것도 허용이 안되기 때문에 가장 긴 줄어드는 부분 수열을 구할 때, 중량이 같지 않은 경우만 허용하는 조건을 넣어줬어야 했다.
하지만 이 문제는 그냥 다이아몬드의 가치가 높아지기만 하면 되는데, 중량이 같아도 선명도가 낮아지면 가치가 높아지는 것으로 볼 것 같으니 굳이 그런 조건은 안 넣어줘도 될 것 같다. (참고로 smart elephant에서는 중량, 선명도 대신, 코끼리의 무게와 지능이었음)
입력받는 부분에서 좀 애먹었는데, 예를 들어 1.5가 들어오면 이것을 정수로 변환한답시고 1*10+5*10을 해놓고 왜 15가 안나오지...하고 있었다... 1*10+5*1인데... 고쳤더니 예제는 잘 나온다. 근데 WA를 받았다...
흠... 아까 내가 처음에 고민했던 문제인 것 같다. 문제 원문을 보니
find the longest subsequence of diamonds for which the weight and clarity are both becoming strictly more favorable to a buyer. 라고 되어있다.
both becoming strictly!! -> 이 부분때문에 아마도 중량이 같을 때 선명도가 낮아지는 경우를 선택하면 안되는 것 같다. 결국 smart elephant랑 똑같다.
다시 고쳐서 제출해 봐야겠다.
계속 틀리다 먼저 푼 친구의 도움을 얻어 겨우 통과시켰다. 바로 이 문제는 smart elephant랑 다른 것이 입력으로 주어진 순서를 지켜야 한다. 그러니까 입력으로 주어진 것에서 골라내서 맞추는 게 아니라 입력으로 주어진 순서를 지키면서 무게가 증가하고, 선명도가 낮아지는 것 부분 수열을 찾아야 한다. 그래서 sort를 제거하고 제출해서 맞았다.
이 문제는... 계속 틀릴 때는 내가 문제를 제대로 이해한 것이 맞는지도 생각해봐야 한다는 교훈을 준 문제이다.
다이아몬드의 중량과 선명도가 주어지면 중량이 늘어나고, 선명도가 줄어들게 다이아몬드를 나열했을 때 최대 길이를 구하는 문제이다.
풀이는 중량 기준으로 오름차순으로 정렬한 목록에서 선명도의 가장 긴 줄어드는 부분 수열의 길이를 구하면 된다. (반대로 선명도 기준으로 내림차순으로 정렬하고 중량의 LIS를 구해도 된다... LIS가 좀 더 익숙하니 이게 더 나을 수도...)
하나 주의할 점은 중량 기준으로 오름차순으로 정렬할 때, 만약 중량이 같다면 선명도가 내림차순 기준으로 정렬되도록 해줘야 할 것이고, 또한 smart elephant에서는 중량이 같고 선명도가 줄어드는 것도 허용이 안되기 때문에 가장 긴 줄어드는 부분 수열을 구할 때, 중량이 같지 않은 경우만 허용하는 조건을 넣어줬어야 했다.
하지만 이 문제는 그냥 다이아몬드의 가치가 높아지기만 하면 되는데, 중량이 같아도 선명도가 낮아지면 가치가 높아지는 것으로 볼 것 같으니 굳이 그런 조건은 안 넣어줘도 될 것 같다. (참고로 smart elephant에서는 중량, 선명도 대신, 코끼리의 무게와 지능이었음)
입력받는 부분에서 좀 애먹었는데, 예를 들어 1.5가 들어오면 이것을 정수로 변환한답시고 1*10+5*10을 해놓고 왜 15가 안나오지...하고 있었다... 1*10+5*1인데... 고쳤더니 예제는 잘 나온다. 근데 WA를 받았다...
흠... 아까 내가 처음에 고민했던 문제인 것 같다. 문제 원문을 보니
find the longest subsequence of diamonds for which the weight and clarity are both becoming strictly more favorable to a buyer. 라고 되어있다.
both becoming strictly!! -> 이 부분때문에 아마도 중량이 같을 때 선명도가 낮아지는 경우를 선택하면 안되는 것 같다. 결국 smart elephant랑 똑같다.
다시 고쳐서 제출해 봐야겠다.
계속 틀리다 먼저 푼 친구의 도움을 얻어 겨우 통과시켰다. 바로 이 문제는 smart elephant랑 다른 것이 입력으로 주어진 순서를 지켜야 한다. 그러니까 입력으로 주어진 것에서 골라내서 맞추는 게 아니라 입력으로 주어진 순서를 지키면서 무게가 증가하고, 선명도가 낮아지는 것 부분 수열을 찾아야 한다. 그래서 sort를 제거하고 제출해서 맞았다.
이 문제는... 계속 틀릴 때는 내가 문제를 제대로 이해한 것이 맞는지도 생각해봐야 한다는 교훈을 준 문제이다.
BOJ 1912 연속합
오랜만에 이 문제를 봤다.
풀이만 간단히 정리해보면...
dp로 풀 수 있는데,
d[idx] = (arr[idx]를 마지막 수로 하는 연속합의 최대값) 으로 놓고 풀면 된다.
풀이만 간단히 정리해보면...
dp로 풀 수 있는데,
d[idx] = (arr[idx]를 마지막 수로 하는 연속합의 최대값) 으로 놓고 풀면 된다.
BOJ 1011 Fly me to the Alpha Centauri
x지점에서 y지점으로 이동할 때, 이동횟수의 최소값을 구하는 문제인데, 중요한 규칙이 하나 있다. 일단 처음에는 1밖에 못움직이고, 이전에 k만큼 움직였다면 다음엔 k-1, k, k+1중 하나로 움직일 수 있고, 마지막에 y에 도달할 때는 1만큼 움직여서 y에 도달해야 한다. 즉 y-1에서 y로 도달해야 한다. 또 그러기 위해서는 y-1까지 오는 움직임은 y-2에서 1만큼 오거나 y-3에서 2만큼 오는 두 가지 경우 밖에 없을 것이다.
x => 1 => x+1 => .... => y-1 => 1 => y
x+1 지점부터 1만큼 갈지 2만큼 갈지 결정하는 것부터 시작해서 y-1에 도착하면 1만큼 갈 수 있게 y-1에 적절한 경로를 거쳐 도착해야 할 것이다.
dp로 해보면 괜찮을 것 같은데 x, y의 범위가 2의 31제곱-1 까지이다... 무려 20억이 넘는 수...
직접 해보면 1 다음에는 1, 2로 움직일 수 있고, 그 다음에는 1-1, 2 / 2-1, 2, 3 ... 이렇게 1보다 큰 수들은 모두 3가지로 나눠질 수 있다. 대략 3의 n제곱 개... 엄청 많은 경우의 수이다.
아 좀 더 생각해보니, dp를 이용하거나 모든 경우를 다 해볼 필요가 없어보이는 것이... 최소로 움직여야 하고, 그리고 시작 움직임과 끝 움직임이 1이여야 한다. 또한 한 번에 늘리거나 줄일 수 있는 거리도 1밖에 안된다. 즉 일단은 1부터 시작해서 최소로 움직이려면 1, 2, 3, 4... 이렇게 움직이는 거리를 늘려나가야 하는데 무작정 늘리면 안되는 것이 마지막 움직임은 1이 되야하므로 어느정도까지 늘렸다가 줄여야 하는데, 줄일 때는 한 번에 1씩밖에 못 줄인다. 그렇기 때문에 늘리는 것은 중간지점까지 밖에 못 늘리고(중간 지점을 넘어서까지 늘리면 마지막에 1로 움직일 수 없다), 중간지점까지 최대한 1씩 늘렸다가 중간에서 1씩 줄이는 것이 최소한으로 움직일 수 있는 방법이 될 것이다.
음 처음엔 dp인가... 모든 경우를 다 고려해 봐야하나.. 했는데 이렇게 시작과 끝의 움직이는 거리 조건이 1로 주어진 것이나 한 번에 늘리거나 줄일 수 있는 거리가 1밖에 안된다는 점.. 그리고 최소로 움직이는 횟수를 구해야 한다는 점들 때문에 이렇게 풀 수 있게 되는 것 같다. 멋있는 문제다.
자 그럼 구현은 어떻게 할까? x, y가 주어지면 y-x값을 가지고 작업을 시작한다.
일단 1부터 n까지의 합은 n*(n+1)/2로 나타낼 수 있는데 n이 5만(50000)일 때, 즉 1부터 50000까지의 합이 1,250,025,000 으로 12억이 넘는다. 2의 31제곱이 약 22억정도 이므로 대충 50000까지의 누적합만 이용해도 충분하다.
50000까지의 누적합을 미리 구해놓고(그냥 n*(n+1)/2), 양쪽에서 1, 2, 3... 이렇게 움직인다고 생각하면
y-x >= psum[x]*2 인 최대의 x를 찾는다. 만약 y-x=psum[x]*2라면 답은 x*2가 될 것이고, 아니라면 음... 여러가지 경우가 생길 수 있어보인다. 고민하다가 맞은 사람 목록을 봤는데, 코드들이 상당히 짧다. 질문 게시판도 봐야겠다. 다른 분들의 글을 대충 봤는데, 규칙을 이용하거나 수식으로 간단하게 푸시는 것 같다. 좀 더 고민해 봐야겠다.
결국 검색을 통해 isac322님의 코드를 봤다. 와 엄청 간단하고 짧고... 코드를 보면서 어떻게 이렇게? 라는 생각이 들었지만 잘 생각해보니 맞다.... 아 난 왜 이런 생각을 못했을까라는 생각도 들지만, 그 전에 다른 방법으로도 짠 사람들 많던데 난 다른 방법도 생각 못했다.
접근은 위에서 생각한 것과 비슷하다. y-x >=psum[x]*2 인 최대의 x를 찾는데, 문제가 되는 부분은 y-x > psum[x]*2일 때, (y-x)-psum[x]*2값을 어떻게 처리하냐였다. 여기서 어떻게 할 것인가? (y-x)-psum[x]*2==k라고 하자. k값은psum[x+1]*2보단 (x+1)*2보단 작은 값일 것이다. 만약 k값이 psum[x+1]값 (x+1)과 같다면 x*2+1이 답이될 것이다. 여기까지는 쉽다. 자 이제 잘 생각해야 한다. 만약 k값이 psum[x+1]값 (x+1)보다 작은 경우와 k값이 psum[x+1] (x+1)보다 큰 경우가 있는데 둘 다 결론부터 말하면 답은 각각 x*2+1, x*2+2가 된다.
k값이psum[x+1] (x+1)보다 작은 경우부터 보자. 지금 상태를 보면 k값을 중간에 놔두고, k값 양쪽에서 1+ 2+ 3.+..+x 만큼 온 상태이다. k값이 x-1이라면 가능하겠지만, x와 차이가 크다면? 그럼 처음부터 모든 경우를 해봐야 하는 것 아닐까? 아니다. 그럴 필요 없다. k이전 값이든 이후 값이든 하나를 기준으로 잡자. k 이전 값들을 기준으로 잡고 k값이 x값과 차이가 1이 나도록 이전 값들을 다 1씩 줄인다. 만약 이전 값중에 3개의 값만 1씩 줄이면 k값은 3이 늘어날 것이다. 맨 처음 시작 값인 1은 못 줄인다해도 2부터 줄이기만 해도 x-1만큼의 길이를 확보할 수 있다. 즉 k값이 최대 x-1만큼 늘어날 수 있다는 것이다. 만약 양 쪽다 조정한다면 더 많이 늘어날 수 있지만 그럴 필요는 없고, 만약 k가 1이라해도 x-1만큼 늘어나면 x가 된다.
그래서 k도 수용할 수 있게 되고, 결국 답은 2*x+1이 되는 것이다.
그리고 k값이psum[x+1] (x+1)보다 큰 경우도 마찬가지다. (설명 생략)
왼쪽, 오른쪽 수와는 0 또는 1이 차이나야 해서 1+2+3...+x인 상태에서는 2부터 x까지 1씩 줄여줌으로써 x-1만큼을 늘려줄 수가 있다.(물론 더 늘릴 수도 있지만 k가 1로 가장 작은 경우에도 x-1만큼만 늘리면 된다)
그리고 이렇게 하면 최소값이 될까? 일단 1+2+3+..이렇게 온 것 자체는 최소값의 페이스대로 한 것이다. 그리고 거기서 1을 더해준 것인데, 최소값이 될 수 밖에 없는 게, 최소값의 페이스 했는데도 k가 남았다면 어떻게 오든지 간에 (최소값의 페이스의 경우) + 1보다 작을 수가 없다.
비록 내가 생각하지는 못했지만 좋은 깨달음을 얻었고, 멋진 문제같다.
그리고 github에 isac322님이 공개해주신 코드를 보고 깨달음을 얻을 수 있었다.
구현해 봐야겠다.
주의할 점으로 psum[x]*2 부분에서 int 형 범위를 넘어갈 수 있기 때문에 long long으로 처리해야 한다.
AC를 받았다.
x => 1 => x+1 => .... => y-1 => 1 => y
x+1 지점부터 1만큼 갈지 2만큼 갈지 결정하는 것부터 시작해서 y-1에 도착하면 1만큼 갈 수 있게 y-1에 적절한 경로를 거쳐 도착해야 할 것이다.
dp로 해보면 괜찮을 것 같은데 x, y의 범위가 2의 31제곱-1 까지이다... 무려 20억이 넘는 수...
직접 해보면 1 다음에는 1, 2로 움직일 수 있고, 그 다음에는 1-1, 2 / 2-1, 2, 3 ... 이렇게 1보다 큰 수들은 모두 3가지로 나눠질 수 있다. 대략 3의 n제곱 개... 엄청 많은 경우의 수이다.
아 좀 더 생각해보니, dp를 이용하거나 모든 경우를 다 해볼 필요가 없어보이는 것이... 최소로 움직여야 하고, 그리고 시작 움직임과 끝 움직임이 1이여야 한다. 또한 한 번에 늘리거나 줄일 수 있는 거리도 1밖에 안된다. 즉 일단은 1부터 시작해서 최소로 움직이려면 1, 2, 3, 4... 이렇게 움직이는 거리를 늘려나가야 하는데 무작정 늘리면 안되는 것이 마지막 움직임은 1이 되야하므로 어느정도까지 늘렸다가 줄여야 하는데, 줄일 때는 한 번에 1씩밖에 못 줄인다. 그렇기 때문에 늘리는 것은 중간지점까지 밖에 못 늘리고(중간 지점을 넘어서까지 늘리면 마지막에 1로 움직일 수 없다), 중간지점까지 최대한 1씩 늘렸다가 중간에서 1씩 줄이는 것이 최소한으로 움직일 수 있는 방법이 될 것이다.
음 처음엔 dp인가... 모든 경우를 다 고려해 봐야하나.. 했는데 이렇게 시작과 끝의 움직이는 거리 조건이 1로 주어진 것이나 한 번에 늘리거나 줄일 수 있는 거리가 1밖에 안된다는 점.. 그리고 최소로 움직이는 횟수를 구해야 한다는 점들 때문에 이렇게 풀 수 있게 되는 것 같다. 멋있는 문제다.
자 그럼 구현은 어떻게 할까? x, y가 주어지면 y-x값을 가지고 작업을 시작한다.
일단 1부터 n까지의 합은 n*(n+1)/2로 나타낼 수 있는데 n이 5만(50000)일 때, 즉 1부터 50000까지의 합이 1,250,025,000 으로 12억이 넘는다. 2의 31제곱이 약 22억정도 이므로 대충 50000까지의 누적합만 이용해도 충분하다.
50000까지의 누적합을 미리 구해놓고(그냥 n*(n+1)/2), 양쪽에서 1, 2, 3... 이렇게 움직인다고 생각하면
y-x >= psum[x]*2 인 최대의 x를 찾는다. 만약 y-x=psum[x]*2라면 답은 x*2가 될 것이고, 아니라면 음... 여러가지 경우가 생길 수 있어보인다. 고민하다가 맞은 사람 목록을 봤는데, 코드들이 상당히 짧다. 질문 게시판도 봐야겠다. 다른 분들의 글을 대충 봤는데, 규칙을 이용하거나 수식으로 간단하게 푸시는 것 같다. 좀 더 고민해 봐야겠다.
결국 검색을 통해 isac322님의 코드를 봤다. 와 엄청 간단하고 짧고... 코드를 보면서 어떻게 이렇게? 라는 생각이 들었지만 잘 생각해보니 맞다.... 아 난 왜 이런 생각을 못했을까라는 생각도 들지만, 그 전에 다른 방법으로도 짠 사람들 많던데 난 다른 방법도 생각 못했다.
접근은 위에서 생각한 것과 비슷하다. y-x >=psum[x]*2 인 최대의 x를 찾는데, 문제가 되는 부분은 y-x > psum[x]*2일 때, (y-x)-psum[x]*2값을 어떻게 처리하냐였다. 여기서 어떻게 할 것인가? (y-x)-psum[x]*2==k라고 하자. k값은
k값이
그래서 k도 수용할 수 있게 되고, 결국 답은 2*x+1이 되는 것이다.
그리고 k값이
왼쪽, 오른쪽 수와는 0 또는 1이 차이나야 해서 1+2+3...+x인 상태에서는 2부터 x까지 1씩 줄여줌으로써 x-1만큼을 늘려줄 수가 있다.(물론 더 늘릴 수도 있지만 k가 1로 가장 작은 경우에도 x-1만큼만 늘리면 된다)
그리고 이렇게 하면 최소값이 될까? 일단 1+2+3+..이렇게 온 것 자체는 최소값의 페이스대로 한 것이다. 그리고 거기서 1을 더해준 것인데, 최소값이 될 수 밖에 없는 게, 최소값의 페이스 했는데도 k가 남았다면 어떻게 오든지 간에 (최소값의 페이스의 경우) + 1보다 작을 수가 없다.
비록 내가 생각하지는 못했지만 좋은 깨달음을 얻었고, 멋진 문제같다.
그리고 github에 isac322님이 공개해주신 코드를 보고 깨달음을 얻을 수 있었다.
구현해 봐야겠다.
주의할 점으로 psum[x]*2 부분에서 int 형 범위를 넘어갈 수 있기 때문에 long long으로 처리해야 한다.
AC를 받았다.
BOJ 2243 사탕 상자
빈 사탕 상자에서 시작해서 주어진 입력에 따라 우선순위가 a인 사탕을 b개 넣거나 뺀다(먹지는 않음). 그러면서 도중에 우선순위가 x번째로 높은 사탕을 빼서 먹을 것인데, 빼서 먹게 되는 사탕의 우선순위를 출력하는 것이 문제이다.
일단 priority queue(-1을 곱해서 넣고 뺄 때 -1을 붙여서 min heap으로 활용)를 활용해서 하면 될 것 같아보이는데, 좀 걸리는 게 사탕의 총 개수가 최대 20억개라는 것이다. 예를 들어 10억번째로 우선순위가 높은 사탕이 뭔지 찾으라고 하면 priority queue에서 10억 번을 빼야하나? 음 아니다! 입력으로 주어지는 사탕을 넣고 빼고 하는 횟수의 수가 최대 10만 번이다. 그렇다는 것은 일단 prirority queue에는 (사탕의 우선순위, 그 사탕의 개수)가 최대 10만 개 들어가있다는 것이다. 음 그래도 query까지 하면 시간이 꽤 걸릴 것 같은데...
아... 굳이 priority queue를 쓸 필요가 없다. 우선순위는 최대 백만까지다. 그냥 배열의 인덱스로 우선순위를 표시하고 배열에는 그 우선순위에 해당하는 사탕의 개수를 기록해도 될 것이다. 그럼 찾는 것은 어떻게 빨리 찾을 수 있을까? 누적합을 이용해서 이분탐색을 하면 빠르게 찾을 수 있을 것이다. 그런데 누적합의 업데이트가 빈번하다... 그렇다면 fenwick tree를 쓰면 어떨까? 한 번 구현해 봐야겠다. 예제 케이스도 제대로 안 나오길래 봤더니 이분 탐색이 문제였다. 이분 탐색을 구현할 때 좀 헷갈리고 까다로웠는데, 주의해야 한다.
AC를 받았다!
Fenwick Tree를 이용해서 누적합을 logN만에 업데이트 할 수 있고, 이분 탐색을 이용해서 x번째로 우선순위가 높은 사탕을 logN(이분탐색)*logN(누적합 구하기)만에 찾을 수 있다.(N은 100만)
일단 priority queue(-1을 곱해서 넣고 뺄 때 -1을 붙여서 min heap으로 활용)를 활용해서 하면 될 것 같아보이는데, 좀 걸리는 게 사탕의 총 개수가 최대 20억개라는 것이다. 예를 들어 10억번째로 우선순위가 높은 사탕이 뭔지 찾으라고 하면 priority queue에서 10억 번을 빼야하나? 음 아니다! 입력으로 주어지는 사탕을 넣고 빼고 하는 횟수의 수가 최대 10만 번이다. 그렇다는 것은 일단 prirority queue에는 (사탕의 우선순위, 그 사탕의 개수)가 최대 10만 개 들어가있다는 것이다. 음 그래도 query까지 하면 시간이 꽤 걸릴 것 같은데...
아... 굳이 priority queue를 쓸 필요가 없다. 우선순위는 최대 백만까지다. 그냥 배열의 인덱스로 우선순위를 표시하고 배열에는 그 우선순위에 해당하는 사탕의 개수를 기록해도 될 것이다. 그럼 찾는 것은 어떻게 빨리 찾을 수 있을까? 누적합을 이용해서 이분탐색을 하면 빠르게 찾을 수 있을 것이다. 그런데 누적합의 업데이트가 빈번하다... 그렇다면 fenwick tree를 쓰면 어떨까? 한 번 구현해 봐야겠다. 예제 케이스도 제대로 안 나오길래 봤더니 이분 탐색이 문제였다. 이분 탐색을 구현할 때 좀 헷갈리고 까다로웠는데, 주의해야 한다.
AC를 받았다!
Fenwick Tree를 이용해서 누적합을 logN만에 업데이트 할 수 있고, 이분 탐색을 이용해서 x번째로 우선순위가 높은 사탕을 logN(이분탐색)*logN(누적합 구하기)만에 찾을 수 있다.(N은 100만)
BOJ 4348 막대 정사각형
길이가 다양한 N개의 막대가 주어지고, 그 막대들을 모두 이용해서 정사각형을 만들 수 있는지 없는지를 구하는 문제이다.
정사각형은 네 변의 길이가 같기 때문에 주어진 막대들의 합을 4로 나눈 값이 정사각형의 한 변의 길이가 될 것이다. (주어진 막대들이 합이 홀수이면 no출력)
한 변의 길이 len을 구하게 되면 이제 주어진 막대들을 한 번씩 이용해서 len을 4개 만들 수 있는지 따져봐야 한다. 이제 이 부분에서 매우 많은 경우가 나오고 겹치기 때문에 dp(memoization)로 처리해주는데, 비트마스크를 활용해서 어떤 막대기를 사용했는지 상태를 표시해준다. 막대기의 개수가 최대 20개이므로 상태를 비트로 표현할 수 있다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지.
d[state]=(d[nextState1] || d[nextState2] || ...); 하나라도 true이면 true, 모두 false이면 false.
직접 구현을 해보면서 생각해 봐야겠다.
일단 구현해서 제출했는데 AC를 받았다! 내 풀이를 적어보겠다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지인데, dp를 구현하는 재귀함수에 parameter로 state와 한 변의 남은 길이, 만들어야할 변의 개수 를 보냈다.(정사각형 한 변의 길이는 전역변수로 처리) 정사각형에는 총 4개의 변이 있고, 한 변씩 만들어 갈 것인데 state를 보고 아직 선택하지 않은 막대기를 골라서 정사각형의 변을 하나씩 만들어 가는 식이다. 처음에는 한 변의 남은 길이로 정사각형의 변의 길이가 들어올 것이고, 그럼 아직 선택되지 않은 막대기 중 그 길이보다 짧은, 혹은 같은 막대기를 선택해서 state에 선택했다고 표시해주고, 한 변의 남은 길이(정사각형의 변의 길이)에서 선택한 막대기의 길이를 빼서 다음 함수의 "한 변의 남은 길이"로 보내준다. 이렇게 해서 한 변이 다 만들어지면 그 때, 또 하나의 parameter인 만들어야할 변의 개수를 -1 해준다.
그러니까 처음에는 dp(state : 0, remained : len, num : 4) 이렇게 시작한다.
그래서 기저 조건으로는 num이 0이되면 정사각형이 완성된 것이므로 return 1을 해준다.
정사각형을 완성 못했는데 더이상 선택할 것이 없는 경우는 자동으로 return 0이 된다.
그리고 계산을 위해 paramter로 여러 개를 보내줬지만 d[state]하나로 memoization이 가능한 것은 어떤 변을 선택했냐에 따라서 만들 수 있는 변의 개수나 남은 길이는 다 똑같이 정해지기 때문이다!
정사각형은 네 변의 길이가 같기 때문에 주어진 막대들의 합을 4로 나눈 값이 정사각형의 한 변의 길이가 될 것이다. (주어진 막대들이 합이 홀수이면 no출력)
한 변의 길이 len을 구하게 되면 이제 주어진 막대들을 한 번씩 이용해서 len을 4개 만들 수 있는지 따져봐야 한다. 이제 이 부분에서 매우 많은 경우가 나오고 겹치기 때문에 dp(memoization)로 처리해주는데, 비트마스크를 활용해서 어떤 막대기를 사용했는지 상태를 표시해준다. 막대기의 개수가 최대 20개이므로 상태를 비트로 표현할 수 있다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지.
d[state]=(d[nextState1] || d[nextState2] || ...); 하나라도 true이면 true, 모두 false이면 false.
직접 구현을 해보면서 생각해 봐야겠다.
일단 구현해서 제출했는데 AC를 받았다! 내 풀이를 적어보겠다.
d[state]=현재 상태 state에서 시작할 때, 정사각형을 만들 수 있는지 없는지인데, dp를 구현하는 재귀함수에 parameter로 state와 한 변의 남은 길이, 만들어야할 변의 개수 를 보냈다.(정사각형 한 변의 길이는 전역변수로 처리) 정사각형에는 총 4개의 변이 있고, 한 변씩 만들어 갈 것인데 state를 보고 아직 선택하지 않은 막대기를 골라서 정사각형의 변을 하나씩 만들어 가는 식이다. 처음에는 한 변의 남은 길이로 정사각형의 변의 길이가 들어올 것이고, 그럼 아직 선택되지 않은 막대기 중 그 길이보다 짧은, 혹은 같은 막대기를 선택해서 state에 선택했다고 표시해주고, 한 변의 남은 길이(정사각형의 변의 길이)에서 선택한 막대기의 길이를 빼서 다음 함수의 "한 변의 남은 길이"로 보내준다. 이렇게 해서 한 변이 다 만들어지면 그 때, 또 하나의 parameter인 만들어야할 변의 개수를 -1 해준다.
그러니까 처음에는 dp(state : 0, remained : len, num : 4) 이렇게 시작한다.
그래서 기저 조건으로는 num이 0이되면 정사각형이 완성된 것이므로 return 1을 해준다.
정사각형을 완성 못했는데 더이상 선택할 것이 없는 경우는 자동으로 return 0이 된다.
그리고 계산을 위해 paramter로 여러 개를 보내줬지만 d[state]하나로 memoization이 가능한 것은 어떤 변을 선택했냐에 따라서 만들 수 있는 변의 개수나 남은 길이는 다 똑같이 정해지기 때문이다!
BOJ 2231 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미하고, 어떤 자연수 M의 분해합이 N이면 M을 N의 생성자라고 한다.
예를 들어, 245의 분해합은 245+2+4+5=256이 되고, 245가 256의 생성자가 된다. 자연수마다 생성자가 없을 수도 있고, 여러개 있을 수도 있는데, 이 문제는 입력으로 어떤 자연수가 주어지면 그 자연수의 생성자 중 최소값을 구하는 문제이다. (생성자가 없다면 0 출력)
일단 N 제한은 100만이다. 그리고 어떤 자연수 n의 생성자는 n이하일 수 밖에 없다. 일단 최소값을 구하는 문제이므로 1부터 n까지 다 해보면서 구하면 될 것 같다.
구현해 봐야겠다. AC를 받았다.
다른 분들 풀이를 보니까 n이 70보다 클 경우 1부터 보지않고, n-70부터 보는데, 생각해보니 최대 100만이므로 7자리 수인데, 분해할 경우 한 자리의 최대값은 9이다. 그래서 더해질 수 있는 합의 최대값을 대략 10*7로 하신 것 같고 70보다 큰 값이 들어오면 70이전부터만 보는 것 같다. 좀 더 정확히는 9*6만 해도 될 것 같다. 100만이 최고이므로 그 이전 수들은 6자리 수이므로... 한 번 9*6으로 해서 제출해 봐야겠다. AC를 받았다. 100만번 돌던 것을 70번밖에 안도니 확실히 시간이 확 줄어든다.
예를 들어, 245의 분해합은 245+2+4+5=256이 되고, 245가 256의 생성자가 된다. 자연수마다 생성자가 없을 수도 있고, 여러개 있을 수도 있는데, 이 문제는 입력으로 어떤 자연수가 주어지면 그 자연수의 생성자 중 최소값을 구하는 문제이다. (생성자가 없다면 0 출력)
일단 N 제한은 100만이다. 그리고 어떤 자연수 n의 생성자는 n이하일 수 밖에 없다. 일단 최소값을 구하는 문제이므로 1부터 n까지 다 해보면서 구하면 될 것 같다.
구현해 봐야겠다. AC를 받았다.
다른 분들 풀이를 보니까 n이 70보다 클 경우 1부터 보지않고, n-70부터 보는데, 생각해보니 최대 100만이므로 7자리 수인데, 분해할 경우 한 자리의 최대값은 9이다. 그래서 더해질 수 있는 합의 최대값을 대략 10*7로 하신 것 같고 70보다 큰 값이 들어오면 70이전부터만 보는 것 같다. 좀 더 정확히는 9*6만 해도 될 것 같다. 100만이 최고이므로 그 이전 수들은 6자리 수이므로... 한 번 9*6으로 해서 제출해 봐야겠다. AC를 받았다. 100만번 돌던 것을 70번밖에 안도니 확실히 시간이 확 줄어든다.
2016년 9월 29일 목요일
BOJ 2405 세 수, 두 M
세 수의 중위 값은 정렬했을 때 가운데 오는 값이고, 세 수의 평균값은 세 수의 합을 3으로 나눈 값이다. 최대 10만개의 수가 주어질 때, 중위값과 평균값의 차이가 최대가 되도록 세 수를 선택하고, 그 중위값과 평균값의 차이(최대값)를 구하는 문제이다.
음 평균값과 중위값의 차이가 커지려면 어떻게 해야할까?
일단 중위값을 편하게 구하기 위해서 주어진 수들을 오름차순으로 정렬해본다.
100 120 234 430 489 여기서 어떤 세 수를 고르든 중위값은 맨 앞, 맨 뒤 값을 제외한 수들 중 하나가 될 것이다. 중위값을 먼저 선택했다고 치자. 그럼 나머지 수는 중위값의 왼쪽에서 하나, 오른쪽에서 하나를 골라야 한다. 어떤 수를 골라야 평균값이 중위값에서 멀어질까? 일단 b값은 정해졌으니 a, c값만 생각하자. a+c값이 최대한 크거나 최대한 작아야 평균값이 중위값에서 멀어질 것이다. b값은 정해져있고 (a+b+c)/3이 평균이므로 a+c가 최대가 되거나 a+c가 최소가 되는 수를 골라야 평균값이 중위값에서 멀어질 가능성이 높다. (a+c)/2의 값이 b에 가까우면 안되고 최대한 멀어지려면 a+c값이 최대가 되도록 혹은 a+c값이 최소가 되도록한 것 둘 중하나가 b에서 멀 것이다.
막 확실하게 증명할 수 있거나 와 닿는 것은 아니지만... 맞는 것 같다.
그럼 정렬된 상태에서 b(중위값)을 기준으로 왼쪽에서 가장 큰 값, 오른쪽에서 가장 큰 값을 이용해서 값(평균값과 중위값의 차이)을 구해보고, 왼쪽에서 가장 작은 값, 오른쪽에서 가장 작은 값을 이용해서 값을 구해본 후 두 값을 비교해서 둘 중 큰 값을 선택하면 된다.
정렬을 했다면 , 중위값 양쪽 구간의 각 최소값, 최대값은 바로 구할 수 있다.
그럼 중위값을 2번째 값부터 n-1번째 값까지로 보면서 하면 O(n)만에 풀 수 있겠다.
주의할 점은 평균값을 구하기 위해 3으로 나누면 나머지가 버려지므로... 어차피 답에서 3을 곱해서 출력하라고 했으니 평균값을 구할 때 3으로 나누지말고, 그냥 중위값*3과의 차이를 계산하면 될 것 같다.
AC를 받았다.
음 평균값과 중위값의 차이가 커지려면 어떻게 해야할까?
일단 중위값을 편하게 구하기 위해서 주어진 수들을 오름차순으로 정렬해본다.
100 120 234 430 489 여기서 어떤 세 수를 고르든 중위값은 맨 앞, 맨 뒤 값을 제외한 수들 중 하나가 될 것이다. 중위값을 먼저 선택했다고 치자. 그럼 나머지 수는 중위값의 왼쪽에서 하나, 오른쪽에서 하나를 골라야 한다. 어떤 수를 골라야 평균값이 중위값에서 멀어질까? 일단 b값은 정해졌으니 a, c값만 생각하자. a+c값이 최대한 크거나 최대한 작아야 평균값이 중위값에서 멀어질 것이다. b값은 정해져있고 (a+b+c)/3이 평균이므로 a+c가 최대가 되거나 a+c가 최소가 되는 수를 골라야 평균값이 중위값에서 멀어질 가능성이 높다. (a+c)/2의 값이 b에 가까우면 안되고 최대한 멀어지려면 a+c값이 최대가 되도록 혹은 a+c값이 최소가 되도록한 것 둘 중하나가 b에서 멀 것이다.
막 확실하게 증명할 수 있거나 와 닿는 것은 아니지만... 맞는 것 같다.
그럼 정렬된 상태에서 b(중위값)을 기준으로 왼쪽에서 가장 큰 값, 오른쪽에서 가장 큰 값을 이용해서 값(평균값과 중위값의 차이)을 구해보고, 왼쪽에서 가장 작은 값, 오른쪽에서 가장 작은 값을 이용해서 값을 구해본 후 두 값을 비교해서 둘 중 큰 값을 선택하면 된다.
정렬을 했다면 , 중위값 양쪽 구간의 각 최소값, 최대값은 바로 구할 수 있다.
그럼 중위값을 2번째 값부터 n-1번째 값까지로 보면서 하면 O(n)만에 풀 수 있겠다.
주의할 점은 평균값을 구하기 위해 3으로 나누면 나머지가 버려지므로... 어차피 답에서 3을 곱해서 출력하라고 했으니 평균값을 구할 때 3으로 나누지말고, 그냥 중위값*3과의 차이를 계산하면 될 것 같다.
AC를 받았다.
BOJ 2370 시장 선거 포스터
입력으로 포스터를 어디서 부터 어디까지 붙일지(너비)가 주어지고 (모든 포스터의 높이는 같다) 입력으로 주어지는 순서대로 포스터를 붙일 때(겹쳐도 상관없다), 포스터를 다 붙이고 나서 보이는 포스터의 수를 구하는 문제이다.
이것을 전체 너비만큼 배열을 잡고 하면 할만할 것 같은데, 포스터를 붙일 수 있는 곳의 너비가 최대 1억이므로 1억개짜리 int 형 배열로 잡으면 할만해 보이는데 거의 400MB가 된다. 문제의 메모리 제한은 128MB이다.
음 근데, n은 최대 10000이다. 포스터의 최대 개수는 10000개 이므로 입력으로 들어오는 포스터를 순서대로 보면서 앞에 받았던(벽에 먼저 붙인) 포스터들과 비교하면서 개수를 세면 될 것 같기도 하다. 구현해 봐야겠다. 막상 해보니 생각해야할 것이 좀 있다. 앞에 붙였던 포스터들도 그 다음에 붙여지는 포스터들 때문에 가려지는 부분이 생겨서 여러 부분으로 나눠질 수도 있고,,. 음... 그러면 vector를 이용해서 해볼까...
vector를 이용해서 포스터의 왼쪽 끝 위치, 오른쪽 끝 위치를 저장해놓는데, 왜 vector를 이용하냐면, 나중에 붙여지는 포스터들 때문에 이미 붙여놓은 포스터가 가려지면 그 포스터가 여러 부분으로 나눠질 수 있기 때문에 나눠진 것을 다 기록해놔야 하기 때문이다.
나눠지지 않고 가려진다면 그냥 수정만 하면될 것이고, 다 가려진다면 지워버리면 된다. 이렇게 기록을 하면서 새로 들어온 것이나 이미 있던 것이 나눠지면 해당하는 vector배열에 넣고, 완전히 덮어지면 지워버린다. 이렇게 진행하면서 각 포스터의 크기 vector[i].size()가 0이되면 그 포스터는 완전히 덮어진 것이므로 cnt-- 해버리면된다. (새로 들어올 때 cnt++)
제출했는데 한 번 틀려서 출력도 해보고 살펴보니 겹치는 부분을 처리해주는 부분에서 if, else if...로 처리해줬는데, 조건의 순서를 잘 못 배치해서 의도한 바와 다르게 동작하고 있었다. 일단 그 부분을 수정해서 다시 제출을 했다. 요즘 Baekjoon Online Judge의 채점이 좀 오래 걸리는 편이다.
으... 41퍼까지 올라갔다가 틀렸다...
음 틀린 이유를 못 찾겠다...잠시 쉬었다가 다시 봐야겠다.
결국 test case를 살펴보기로 했다... https://webdocs.cs.ualberta.ca/~acpc/2003/ 이 곳에서 테스트 케이스를 받았다. 테스트 케이스가 별로 없기도 하고... 일단 다 제대로 나온다.
강의 시간에 백준님께 한 번 여쭤볼까...
인터넷에 코드가 많은데 랜덤으로 데이터를 만들어서 그 코드들과 비교해볼까 고민 중이다. 지금 랜덤으로 만들어서 비교해보는 중인데, 답이 틀린 경우가 거의 없을 줄 알았는데... 많다. 자주 나온다... 직접 그려보려면 데이터가 작아야 편하니까 데이터 수를 줄이는 중인데 그래도 자주 나온다...잘 나와서 다행이긴 한데... 그 만큼 내 코드가 내 알고리즘이 허술하다는 뜻이니...일단 빨리 왜 틀렸는지 부터 알아봐야겠다.
와... 이유를 찾았다. 정말 내가 틀릴리 없어 -> 아 내가 멍청했구나!!!
내 코드에서 완전히 덮어지거나 겹치거나 나눠지면 vector에서 원래 있던 값을 지워버리는데, 지울 때 vector에서 k번째 값을 지워버리면 한 칸씩 앞으로 당겨지는데, index k는 for문에서 1증가하기 때문에 한 칸 당겨진 것을 안보고 넘어가게 된다!!
그렇기 때문에 꼭 값을 지운 후에는 k--를 해줘야 한다...!!! 일단 고치니 틀렸던 데이터에 대해 답이 맞게 나온다.
제출해 봐야겠다. AC를 받았다.
근데 시간이 너무 오래 걸린다. 다른 분들은 세그먼트 트리를 사용하신 것 같기도 하고, 정렬도 좀 되어있고... 잘 이해는 안가서...강의 시간에 백준님께 설명 잘 들어야겠다.
이것을 전체 너비만큼 배열을 잡고 하면 할만할 것 같은데, 포스터를 붙일 수 있는 곳의 너비가 최대 1억이므로 1억개짜리 int 형 배열로 잡으면 할만해 보이는데 거의 400MB가 된다. 문제의 메모리 제한은 128MB이다.
음 근데, n은 최대 10000이다. 포스터의 최대 개수는 10000개 이므로 입력으로 들어오는 포스터를 순서대로 보면서 앞에 받았던(벽에 먼저 붙인) 포스터들과 비교하면서 개수를 세면 될 것 같기도 하다. 구현해 봐야겠다. 막상 해보니 생각해야할 것이 좀 있다. 앞에 붙였던 포스터들도 그 다음에 붙여지는 포스터들 때문에 가려지는 부분이 생겨서 여러 부분으로 나눠질 수도 있고,,. 음... 그러면 vector를 이용해서 해볼까...
vector를 이용해서 포스터의 왼쪽 끝 위치, 오른쪽 끝 위치를 저장해놓는데, 왜 vector를 이용하냐면, 나중에 붙여지는 포스터들 때문에 이미 붙여놓은 포스터가 가려지면 그 포스터가 여러 부분으로 나눠질 수 있기 때문에 나눠진 것을 다 기록해놔야 하기 때문이다.
나눠지지 않고 가려진다면 그냥 수정만 하면될 것이고, 다 가려진다면 지워버리면 된다. 이렇게 기록을 하면서 새로 들어온 것이나 이미 있던 것이 나눠지면 해당하는 vector배열에 넣고, 완전히 덮어지면 지워버린다. 이렇게 진행하면서 각 포스터의 크기 vector[i].size()가 0이되면 그 포스터는 완전히 덮어진 것이므로 cnt-- 해버리면된다. (새로 들어올 때 cnt++)
제출했는데 한 번 틀려서 출력도 해보고 살펴보니 겹치는 부분을 처리해주는 부분에서 if, else if...로 처리해줬는데, 조건의 순서를 잘 못 배치해서 의도한 바와 다르게 동작하고 있었다. 일단 그 부분을 수정해서 다시 제출을 했다. 요즘 Baekjoon Online Judge의 채점이 좀 오래 걸리는 편이다.
으... 41퍼까지 올라갔다가 틀렸다...
음 틀린 이유를 못 찾겠다...잠시 쉬었다가 다시 봐야겠다.
결국 test case를 살펴보기로 했다... https://webdocs.cs.ualberta.ca/~acpc/2003/ 이 곳에서 테스트 케이스를 받았다. 테스트 케이스가 별로 없기도 하고... 일단 다 제대로 나온다.
강의 시간에 백준님께 한 번 여쭤볼까...
인터넷에 코드가 많은데 랜덤으로 데이터를 만들어서 그 코드들과 비교해볼까 고민 중이다. 지금 랜덤으로 만들어서 비교해보는 중인데, 답이 틀린 경우가 거의 없을 줄 알았는데... 많다. 자주 나온다... 직접 그려보려면 데이터가 작아야 편하니까 데이터 수를 줄이는 중인데 그래도 자주 나온다...잘 나와서 다행이긴 한데... 그 만큼 내 코드가 내 알고리즘이 허술하다는 뜻이니...일단 빨리 왜 틀렸는지 부터 알아봐야겠다.
와... 이유를 찾았다. 정말 내가 틀릴리 없어 -> 아 내가 멍청했구나!!!
내 코드에서 완전히 덮어지거나 겹치거나 나눠지면 vector에서 원래 있던 값을 지워버리는데, 지울 때 vector에서 k번째 값을 지워버리면 한 칸씩 앞으로 당겨지는데, index k는 for문에서 1증가하기 때문에 한 칸 당겨진 것을 안보고 넘어가게 된다!!
그렇기 때문에 꼭 값을 지운 후에는 k--를 해줘야 한다...!!! 일단 고치니 틀렸던 데이터에 대해 답이 맞게 나온다.
제출해 봐야겠다. AC를 받았다.
근데 시간이 너무 오래 걸린다. 다른 분들은 세그먼트 트리를 사용하신 것 같기도 하고, 정렬도 좀 되어있고... 잘 이해는 안가서...강의 시간에 백준님께 설명 잘 들어야겠다.
BOJ 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데
N개의 아이스크림이 있고, 섞어 먹으면 안되는 M개의 아이스크림 조합의 개수가 주어질 때, 섞어 먹으면 안되는 조합을 피해 3개의 아이스크림을 고르는 경우의 수를 구하는 문제이다.
음...섞어 먹으면 안되는 아이스크림의 조합을 포함한 N-3개의 아이스크림을 고르는 경우의 수를 구하는 건 어떨까? 섞어 먹으면 안되는 아이스크림의 조합 하나당 아이스 크림이 2개 포함되어 있으므로 ( (N-2) C (N-3-2) ) * M 이 답이될 것이다.
이게 맞다면 입력으로 받는 N, M만 필요하고 섞어 먹는 아이스크림의 조합은 필요가 없다.
일단 구현해 봐야겠다.
음 틀렸다. 섞어 먹으면 안되는 아이스크림의 조합이 뭐냐가 중요하다.
위의 방법대로 할 경우 입력 예제로 예를 들면 (1, 2), (3, 4) (1, 3)이 섞어 먹으면 안되는 조합인데, (1, 2)를 포함한 N-3개 즉 2개의 아이스크림을 고르는 경우의 수는 (1, 2) 하나인데, 어떻게 이 예제에서는 답은 맞게 나오지만 사실 (1, 2)를 찾았으면 (3, 4, 5)가 답이 되어야하는데 그렇지 않다. (3, 4, 5)는 (3, 4)를 포함하고 있기 때문에 안된다.
다시 처음부터 생각해봐야 겠다.
결국 baactree님의 풀이를 봤다. 이게 N제한이 200이라 O(N세제곱)풀이를 이용하면 된다고 한다. 3중 for문으로 3개의 수를 뽑으면서 M개의 섞어 먹으면 안되는 조합이 포함되어있는 경우는 세지 않으면 된다고 한다. 여기서 M개의 섞어 먹으면 안되는 조합을 어떻게 체크할까 궁금했는데 arr[a][b], arr[b][a]에 기록해 놓으면 O(1)만에 체크할 수 있다... 쉬워 보이지만 난 전혀 생각하지 못했다.
그리고 3중 for문으로 할 경우 조합이 아닌 순열의 개수만큼 나온다. 하지만 중복된 것은 가능한 한 경우당 3*2*1 == 6가지로 같다. 그렇기 때문에 최종적으로 6으로 나누어 주면 된다.
아.. 아니구나 3중 for문으로 할 경우에도 조합을 구할 수 있구나... 처음 알았다.
i=1~n
j=i+1~n
k=j+1~n
이런 식으로 하면 될 것이다.... 헉.. 처음 알았다. 진짜...1을 포함한 조합을 다 구하고, 2를 포함한 조합을 다 구하고... 이렇게 2개짜리 조합(nC2)을 구할 때 처럼 nC3도 마찬가지구나..
good!
이 문제의 풀이를 보면서 느낀게... 내가 실력이 부족한데 그 것을 커버할 수 있는 방법 중 하나가 다양한 문제를 많이 풀어봐서 경험을 많이 쌓는 것인 것 같다.
일단 구현해 봐야겠다.
AC를 받았다. nC3를 , 조합을 for문으로 구현할 수 있다는 것을 알게된 좋은 문제였다.
음...섞어 먹으면 안되는 아이스크림의 조합을 포함한 N-3개의 아이스크림을 고르는 경우의 수를 구하는 건 어떨까? 섞어 먹으면 안되는 아이스크림의 조합 하나당 아이스 크림이 2개 포함되어 있으므로 ( (N-2) C (N-3-2) ) * M 이 답이될 것이다.
이게 맞다면 입력으로 받는 N, M만 필요하고 섞어 먹는 아이스크림의 조합은 필요가 없다.
일단 구현해 봐야겠다.
음 틀렸다. 섞어 먹으면 안되는 아이스크림의 조합이 뭐냐가 중요하다.
위의 방법대로 할 경우 입력 예제로 예를 들면 (1, 2), (3, 4) (1, 3)이 섞어 먹으면 안되는 조합인데, (1, 2)를 포함한 N-3개 즉 2개의 아이스크림을 고르는 경우의 수는 (1, 2) 하나인데, 어떻게 이 예제에서는 답은 맞게 나오지만 사실 (1, 2)를 찾았으면 (3, 4, 5)가 답이 되어야하는데 그렇지 않다. (3, 4, 5)는 (3, 4)를 포함하고 있기 때문에 안된다.
다시 처음부터 생각해봐야 겠다.
결국 baactree님의 풀이를 봤다. 이게 N제한이 200이라 O(N세제곱)풀이를 이용하면 된다고 한다. 3중 for문으로 3개의 수를 뽑으면서 M개의 섞어 먹으면 안되는 조합이 포함되어있는 경우는 세지 않으면 된다고 한다. 여기서 M개의 섞어 먹으면 안되는 조합을 어떻게 체크할까 궁금했는데 arr[a][b], arr[b][a]에 기록해 놓으면 O(1)만에 체크할 수 있다... 쉬워 보이지만 난 전혀 생각하지 못했다.
그리고 3중 for문으로 할 경우 조합이 아닌 순열의 개수만큼 나온다. 하지만 중복된 것은 가능한 한 경우당 3*2*1 == 6가지로 같다. 그렇기 때문에 최종적으로 6으로 나누어 주면 된다.
아.. 아니구나 3중 for문으로 할 경우에도 조합을 구할 수 있구나... 처음 알았다.
i=1~n
j=i+1~n
k=j+1~n
이런 식으로 하면 될 것이다.... 헉.. 처음 알았다. 진짜...1을 포함한 조합을 다 구하고, 2를 포함한 조합을 다 구하고... 이렇게 2개짜리 조합(nC2)을 구할 때 처럼 nC3도 마찬가지구나..
good!
이 문제의 풀이를 보면서 느낀게... 내가 실력이 부족한데 그 것을 커버할 수 있는 방법 중 하나가 다양한 문제를 많이 풀어봐서 경험을 많이 쌓는 것인 것 같다.
일단 구현해 봐야겠다.
AC를 받았다. nC3를 , 조합을 for문으로 구현할 수 있다는 것을 알게된 좋은 문제였다.
2016년 9월 28일 수요일
BOJ 1334 다음 팰린드롬 수
어떤 수 N이 주어질 때, N보다 큰 팰린드롬 수 중에서 가장 작은 수를 구하는 문제이다.
N은 최대 50자리인 양수이다. 문제 분류를 보니 수학, 문자열 처리로 되어있다.
N이 최대 50자리이므로 문자열로 처리하면 될 것이고, 주어진 N보다 큰 팰린드롬 수 중 가장 작은 수를 구하는 것은 N을 변형해서 만들면 될 것 같다.
홀수 자리의 N이 주어진다면 가운데 수 하나를 기준으로 양쪽으로 나눠지는데, 왼쪽(앞쪽)의 수를 변형하지 않고 그것을 기준으로 팰린드롬을 만드는 것이 가장 원래 수와 가까운 수를 만드는 방법일 것이다. 가운데 수 하나를 기준으로 대칭되게 만드는데, 왼쪽의 수를 기준으로 해서 만들어보고 만약 이 값이 더 크면 그것이 답이 되겠지만 크지 않다면 가운데 수를 1증가 시켜주면 될 것이다. 만약 가운데 수가 9라면 가운데 수를 0으로 바꾸고 가운데 수 바로 왼쪽 자리의 수를 1증가 시켜주고 오른쪽도 1증가 시켜주면 될 것이다.
짝수 개의 경우 딱 반으로 나뉘는데, 이것도 역시 왼쪽을 기준으로 팰린드롬을 만드는데 만든 수가 원래 수보다 크지 않다면 왼쪽 수를 1증가 시키고 대칭되게 만들면 될 것이다.
9999같은 것은 왼쪽 99를 1증가 시키면 100 이 되고 이것을 기준으로 만들면 100001이 된다.
문자열이므로 크기 비교는 문자 하나하나를 비교해주면 될 것 같다. 따로 함수를 만드는 게 편할 것 같다.
그리고 구현할 때는 왼쪽 문자열을 기준으로 해서 하면서, 크기 비교시에는 전체를 비교하지 말고 왼쪽 문자열을 거꾸로 보면서 원래 문자열의 오른쪽 문자열과 비교하게 하면 될 것 같다. 그리고 숫자를 만들어서 출력할 필요 없이 왼쪽 문자열이 결정되면 왼쪽 문자열을 출력하고 (가운데 수가 있다면)가운데 수 출력하고 왼쪽 문자열을 거꾸로 출력하면 될 것이다.
직접 구현해 봐야겠다.
구현하는데 꽤 오래 걸렸다. 100줄 정도가 나온다. 으...44퍼까지 갔다가 틀렸다...
길이가 짝수인 9999 같은 경우 내가 구현한대로 하면 100001이 나온다. 10001이 나와야되는데...이런 경우는 처리를 해줘야겠다. 아 홀수도 마찬가지다... 다 처리를 해줘야겠다.
왼쪽값에 1을 더해줬을 때 자리수가 늘어나면 한 자리는 덜 출력하는 것으로 했는데
7-80퍼에서 또 틀렸다... 음...아.. 한 자리 수를 처리 안해줬다..한 자리수는 그냥 출력하면 된다. 아 아니구나 1증가해서 출력해야 하는데, 9의 경우를 생각해서 처리를 해주면 될 것 같다. AC를 받았다.
지금 yukariko님의 코드를 보고 있는데 엄청 간결하고 짧은 코드이다.
보면서 깨달은 것이, 문자열을 비교할 때, 따로 함수 만들 필요 없이 그냥 strcmp를 써도 된다... 그리고 길이가 짝수인 경우 홀수인 경우도 따로 if, else로 구분할 필요 없이 for(i=len/2+len%2... 이런 식으로 한 것도 그렇고.. 음 여러가지로 대단하다. 일단 풀어야 할 문제가 많으니 다음에 풀 수 있으면 다시 풀어봐야겠다.
N은 최대 50자리인 양수이다. 문제 분류를 보니 수학, 문자열 처리로 되어있다.
N이 최대 50자리이므로 문자열로 처리하면 될 것이고, 주어진 N보다 큰 팰린드롬 수 중 가장 작은 수를 구하는 것은 N을 변형해서 만들면 될 것 같다.
홀수 자리의 N이 주어진다면 가운데 수 하나를 기준으로 양쪽으로 나눠지는데, 왼쪽(앞쪽)의 수를 변형하지 않고 그것을 기준으로 팰린드롬을 만드는 것이 가장 원래 수와 가까운 수를 만드는 방법일 것이다. 가운데 수 하나를 기준으로 대칭되게 만드는데, 왼쪽의 수를 기준으로 해서 만들어보고 만약 이 값이 더 크면 그것이 답이 되겠지만 크지 않다면 가운데 수를 1증가 시켜주면 될 것이다. 만약 가운데 수가 9라면 가운데 수를 0으로 바꾸고 가운데 수 바로 왼쪽 자리의 수를 1증가 시켜주고 오른쪽도 1증가 시켜주면 될 것이다.
짝수 개의 경우 딱 반으로 나뉘는데, 이것도 역시 왼쪽을 기준으로 팰린드롬을 만드는데 만든 수가 원래 수보다 크지 않다면 왼쪽 수를 1증가 시키고 대칭되게 만들면 될 것이다.
9999같은 것은 왼쪽 99를 1증가 시키면 100 이 되고 이것을 기준으로 만들면 100001이 된다.
문자열이므로 크기 비교는 문자 하나하나를 비교해주면 될 것 같다. 따로 함수를 만드는 게 편할 것 같다.
그리고 구현할 때는 왼쪽 문자열을 기준으로 해서 하면서, 크기 비교시에는 전체를 비교하지 말고 왼쪽 문자열을 거꾸로 보면서 원래 문자열의 오른쪽 문자열과 비교하게 하면 될 것 같다. 그리고 숫자를 만들어서 출력할 필요 없이 왼쪽 문자열이 결정되면 왼쪽 문자열을 출력하고 (가운데 수가 있다면)가운데 수 출력하고 왼쪽 문자열을 거꾸로 출력하면 될 것이다.
직접 구현해 봐야겠다.
구현하는데 꽤 오래 걸렸다. 100줄 정도가 나온다. 으...44퍼까지 갔다가 틀렸다...
길이가 짝수인 9999 같은 경우 내가 구현한대로 하면 100001이 나온다. 10001이 나와야되는데...이런 경우는 처리를 해줘야겠다. 아 홀수도 마찬가지다... 다 처리를 해줘야겠다.
왼쪽값에 1을 더해줬을 때 자리수가 늘어나면 한 자리는 덜 출력하는 것으로 했는데
7-80퍼에서 또 틀렸다... 음...아.. 한 자리 수를 처리 안해줬다..
지금 yukariko님의 코드를 보고 있는데 엄청 간결하고 짧은 코드이다.
보면서 깨달은 것이, 문자열을 비교할 때, 따로 함수 만들 필요 없이 그냥 strcmp를 써도 된다... 그리고 길이가 짝수인 경우 홀수인 경우도 따로 if, else로 구분할 필요 없이 for(i=len/2+len%2... 이런 식으로 한 것도 그렇고.. 음 여러가지로 대단하다. 일단 풀어야 할 문제가 많으니 다음에 풀 수 있으면 다시 풀어봐야겠다.
BOJ 1347 미로 만들기
주인공이 미로이 어느 한 칸에 남쪽을 향한 상태로 서있고, 그 상태에서 시작해서 R, L은 각각 그 자리에서 방향만 오른쪽, 왼쪽으로 90도 도는 것이며 F는 앞으로 이동하는 것인다.
주인공이 어느 한 칸에서 남쪽을 향해 서있던 상태에서 시작해서 이동할 수 있는 모든 칸으로 이동한 자신의 움직임을 기록해놓은 정보가 입력으로 주어진다. 그러면 그 정보를 보고 미로를 그려서 출력해야 한다. 이동한 칸은 . 으로, 이동하지 않은 칸은 벽이므로 #으로 출력하면 된다. 그리고 미로는 직사각형 격자 모양이고, 주인공은 이동할 수 있는 칸은 모두 방문하므로 주인공이 이동한 칸을 .으로 설정하고 나머지 칸은 모두 다 #으로 설정한 후 출력하면 될 것 같다.
문제 분류를 보니 시뮬레이션이라고 되어있다.
dr [] = {1, 0, -1, 0}; //행
dc[] = {0, -1, 0, 1}; //열
하, 좌, 상, 우
dr[0]=하, dr[1]=좌, dr[2]=상, dr[3]=우
처음에는 남쪽을 보고 있으니 방향을 뜻하는 숫자를 1을 가지고 있는다. 그리고 R이 나오면(방향+1)%4를 해주면 되고, L이 나오면 방향==0일때는 3, 0이 아닐때는 방향-1을 해주면 된다. 그리고 F일 때는 그 방향대로 한 칸 이동한다.
움직이으로 주어지는 문자열의 길이는 50보다 작으므로 F만 계속 있다고 하더라도 최대 49칸이 이동한다. 49+49+1을 행, 열의 길이로 잡고 어디에서 시작할지 모르니까 중앙에서 시작한다. arr[99][99]행렬을 잡고, arr[49][49]에서 시작한다.
이렇게 해서 다 표시를 한 후에는 어떻게 미로의 크기를 알 수 있을까? 바로 문제의 조건에 모든 행과 열에는 이동할 수 있는 칸이 있다고 되어있어서 이동한 표시가 되어있는 칸을 보고 미로의 시작과 끝, 크기를 알 수 있을 것이다.
구현해 봐야겠다.
F가 나오면 움직이기 때문에 움직일 때마다 행, 열의 최소, 최대 범위를 기록하는 변수와 비교해서 행, 열의 최소, 최대 범위를 갱신 해줬다.
그리고 출력할 때 행, 열의 최소, 최대 범위에서 출력해주면 된다.
AC를 받았다.
주인공이 어느 한 칸에서 남쪽을 향해 서있던 상태에서 시작해서 이동할 수 있는 모든 칸으로 이동한 자신의 움직임을 기록해놓은 정보가 입력으로 주어진다. 그러면 그 정보를 보고 미로를 그려서 출력해야 한다. 이동한 칸은 . 으로, 이동하지 않은 칸은 벽이므로 #으로 출력하면 된다. 그리고 미로는 직사각형 격자 모양이고, 주인공은 이동할 수 있는 칸은 모두 방문하므로 주인공이 이동한 칸을 .으로 설정하고 나머지 칸은 모두 다 #으로 설정한 후 출력하면 될 것 같다.
문제 분류를 보니 시뮬레이션이라고 되어있다.
dr [] = {1, 0, -1, 0}; //행
dc[] = {0, -1, 0, 1}; //열
하, 좌, 상, 우
dr[0]=하, dr[1]=좌, dr[2]=상, dr[3]=우
처음에는 남쪽을 보고 있으니 방향을 뜻하는 숫자를 1을 가지고 있는다. 그리고 R이 나오면(방향+1)%4를 해주면 되고, L이 나오면 방향==0일때는 3, 0이 아닐때는 방향-1을 해주면 된다. 그리고 F일 때는 그 방향대로 한 칸 이동한다.
움직이으로 주어지는 문자열의 길이는 50보다 작으므로 F만 계속 있다고 하더라도 최대 49칸이 이동한다. 49+49+1을 행, 열의 길이로 잡고 어디에서 시작할지 모르니까 중앙에서 시작한다. arr[99][99]행렬을 잡고, arr[49][49]에서 시작한다.
이렇게 해서 다 표시를 한 후에는 어떻게 미로의 크기를 알 수 있을까? 바로 문제의 조건에 모든 행과 열에는 이동할 수 있는 칸이 있다고 되어있어서 이동한 표시가 되어있는 칸을 보고 미로의 시작과 끝, 크기를 알 수 있을 것이다.
구현해 봐야겠다.
F가 나오면 움직이기 때문에 움직일 때마다 행, 열의 최소, 최대 범위를 기록하는 변수와 비교해서 행, 열의 최소, 최대 범위를 갱신 해줬다.
그리고 출력할 때 행, 열의 최소, 최대 범위에서 출력해주면 된다.
AC를 받았다.
BOJ 1374 강의실
N개의 강의와 각 강의의 시작 시간과 종료 시간이 주어진다. 이 때, N개의 강의를 진행하는 데 필요한 최소의 강의실 개수를 구하는 문제이다.
고민하다가 질문 게시판을 봤는데, 시작 시간과 종료 시간을 따로 정렬해놓고 각 수업이 아닌 시간의 흐름에 따라서 생각해보라는 답변이 있어서 일단 각 강의의 시작 시간과 종료 시간을 따로 정렬해놓고 생각해봤다.
고민하다가 질문 게시판을 봤는데, 시작 시간과 종료 시간을 따로 정렬해놓고 각 수업이 아닌 시간의 흐름에 따라서 생각해보라는 답변이 있어서 일단 각 강의의 시작 시간과 종료 시간을 따로 정렬해놓고 생각해봤다.
8 6 15 21 7 20 25 1 3 8 3 2 14 8 6 27 2 7 13 4 12 18 5 6 20
문제의 입력 예제를 가지고 시작 시간과 종료 시간을 따로 정렬해보면
시작 시간 : 2 3 6 6 7 12 15 20
종료 시간 : 8 13 14 18 20 21 25 27
뭔가 해보고 싶은 느낌이 든다. 바로 종료시간과 시작시간을 연결하는 것이다.
종료시간 8이상의 가장 작은 시작시간은 12이다. 그리고 13 -> 15, 14->20 이렇게
연결 하면 연결되지 않은 2 3 6 6 7 이렇게 5개의 시작시간이 남는데 바로 5개가
필요한 강의실의 최소 개수이다.
사실 처음에는 저렇게 그려놓고 연결해보니 느낌으로는 연결되지 않은 것의 개수가
답이라는 것을 알겠는데, 왜 답인지는 바로 생각이 나지 않았다. 고민하다가 (사실
여전히 좀 헷갈리지만) 깨달음을 얻었는데, 자 설명을 해보겠다.
일단 종료시간과 시작시간을 연결할 때는 종료시간 이상의 가장 작은 시작시간과
연결해야 한다. 그래야 최대한 많은 연결을 할 수 있기 때문이다. 그렇다면 연결하는
것은 무슨 의미일까? 종료시간과 시작시간을 연결할 수 있다는 것은 강의실을 바꾸지
않고 이어서 쓸 수 있다는 의미이다. 여기까지는 쉽다.
이제 종료시간과 연결된 시작시간을 보자. 종료시간과 연결된 시작시간은 방금 말했듯이
원래 누가 쓰던 강의실에서 시작하는 것을 의미한다. 그렇다면 종료시간과 연결되지 못한
시작시간은 무엇을 의미할까? 이것이 중요하다. 종료시간과 연결되지 못한 시작시간은
누군가 쓰던 강의실을 이어서 쓰기에는 시간이 안 맞기 때문에(혹은 첫 강의라서) 새로운
강의실을 써야한다는 것을 의미한다.
즉 연결되지 않은 시작시간의 최소 개수는 새로운 강의실을 써야하는 최소 경우이고,
N개의 강의를 진행하는데 필요한 강의실 개수의 최소값이 된다.
그 답변의 도움이 있어서 여기까지 생각할 수 있었다... 풀어봐야겠다.
AC를 받았다.
BOJ 1073 도미노
두 개의 숫자(0~9)가 적혀있는 도미노가 있다. 뒤집을 수 있어서
예를 들면 [1 | 2] 나 [2 | 1]나 같은 것이고, 최대 45개(10 C 2)가 있다.
입력으로 도미노가 주어지면, 주어진 도미노를 모두 이용해서 만들 수 있는 사이클의 집합을 사이클 콜렉션이라고 하는데, 이 사이클 콜렉션의 개수를 구하는 문제이다.
사이클은 [1 | 2][2 | 1] -> 이런 식으로 i 번째 조각의 오른쪽 번호와 i 번째 조각의 왼쪽 번호가 같아야하고 맨 오른쪽 번호와 맨 왼쪽 번호도 같아야 한다.
예를 들면 [1 | 2] 나 [2 | 1]나 같은 것이고, 최대 45개(10 C 2)가 있다.
입력으로 도미노가 주어지면, 주어진 도미노를 모두 이용해서 만들 수 있는 사이클의 집합을 사이클 콜렉션이라고 하는데, 이 사이클 콜렉션의 개수를 구하는 문제이다.
사이클은 [1 | 2][2 | 1] -> 이런 식으로 i 번째 조각의 오른쪽 번호와 i 번째 조각의 왼쪽 번호가 같아야하고 맨 오른쪽 번호와 맨 왼쪽 번호도 같아야 한다.
BOJ 1062 가르침
"anta"로 시작해 "tica"로 끝나는 N개의 단어가 주어지고 k가 주어지는데, (k개의 글자를 잘 선택해서) k개의 글자(알파벳)만으로 구성된 단어의 최대 개수를 구해야 한다.
일단 "anta"와 "tica"가 포함된 단어를 읽기 위해서는 a, c, i, n, t 이렇게 5개의 글자가 필요하다. 저 5개의 글자는 반드시 필요하다. 그렇기 때문에 k가 5보다 작으면 읽을 수 있는 단어의 개수는 0이다.
N제한이 50이고, 단어의 길이도 최대 15이므로 일일이 다 보면 될 것 같다. 구현이 쉬워보이지는 않지만... 구현해 봐야겠다.
일단 체크배열을 이용해서 각 단어마다 어떤 글자가 필요한지 기록을 했다.
그리고 이제 어떻게 할 것인가? 음... 가장 많이 겹치는 글자를 우선적으로 선택해서는 최대값을 얻을 수 없다. 왜냐하면 abcd, abc, acd, x, y 이렇게 5개의 단어가 있다고 하면 k=2일 때, x, y를 k개의 글자로 선택해야 읽을 수 있는 단어가 x, y 2개로 최대가 된다.
많이 겹쳐도 결국 단어를 읽으려면 단어가 포함하는 모든 글자가 필요하기 때문이다...
결국 모든 가능한 경우를 다 해보는 것이 가장 먼저 떠오르는 방법이다. 너무 경우의 수가 많지 않을까 하는 생각이 들긴하지만 생각해보면 그렇지도 않다.
일단 어떤 모든 가능한 경우를 다 해볼 것인가?
주어진 k의 수대로 가능한 모든 경우의 k글자를 정한 후 몇개의 단어를 읽을 수 있는지 비교해본다. k글자 정하는 경우의 수가 매우 많아 보이는데, 다행히 순열은 아니다. 그냥 고르는 것이기 때문에 조합이 될 것이다. 최대한 줄이기 위해서 문제를 잘 읽어보면 "anta"와 "tica"는 양 끝에 항상 포함되어있다. 그렇기 때문에 a, c, i, n, t이 5개의 글자는 반드시 필요하다.5이상의 k가 주어지면 일단 k-5에 대해서만 보면 되고, 주어진 단어들은 미리 비교하기 편하게 앞, 뒤 "anta"와 "tica"를 빼버리자.
이렇게 되면 알파벳 소문자 숫자는 최대 26이었는데 a, c, i, n, t 5 글자를 빼면 21개의 글자 중에서만 고르면 된다. k글자의 가능한 모든 경우의 수는 최대 21 C (k-5) 가 될 것이다.
시간 제한안에는 충분히 들어올 수 있을 것 같긴하다.
근데 21 C (k-5)의 경우의 수를 구현하는 것이 어려워보인다... 음 일단 문제 분류를 한 번 봐야겠다. 헉 보니까 문자열 처리, 시뮬레이션, 부르트포스... 내가 생각한 방식이 맞을 수도 있겠다.
일단 넘기고 다른 문제를 살펴봐야겟다.
일단 "anta"와 "tica"가 포함된 단어를 읽기 위해서는 a, c, i, n, t 이렇게 5개의 글자가 필요하다. 저 5개의 글자는 반드시 필요하다. 그렇기 때문에 k가 5보다 작으면 읽을 수 있는 단어의 개수는 0이다.
N제한이 50이고, 단어의 길이도 최대 15이므로 일일이 다 보면 될 것 같다. 구현이 쉬워보이지는 않지만... 구현해 봐야겠다.
일단 체크배열을 이용해서 각 단어마다 어떤 글자가 필요한지 기록을 했다.
그리고 이제 어떻게 할 것인가? 음... 가장 많이 겹치는 글자를 우선적으로 선택해서는 최대값을 얻을 수 없다. 왜냐하면 abcd, abc, acd, x, y 이렇게 5개의 단어가 있다고 하면 k=2일 때, x, y를 k개의 글자로 선택해야 읽을 수 있는 단어가 x, y 2개로 최대가 된다.
많이 겹쳐도 결국 단어를 읽으려면 단어가 포함하는 모든 글자가 필요하기 때문이다...
결국 모든 가능한 경우를 다 해보는 것이 가장 먼저 떠오르는 방법이다. 너무 경우의 수가 많지 않을까 하는 생각이 들긴하지만 생각해보면 그렇지도 않다.
일단 어떤 모든 가능한 경우를 다 해볼 것인가?
주어진 k의 수대로 가능한 모든 경우의 k글자를 정한 후 몇개의 단어를 읽을 수 있는지 비교해본다. k글자 정하는 경우의 수가 매우 많아 보이는데, 다행히 순열은 아니다. 그냥 고르는 것이기 때문에 조합이 될 것이다. 최대한 줄이기 위해서 문제를 잘 읽어보면 "anta"와 "tica"는 양 끝에 항상 포함되어있다. 그렇기 때문에 a, c, i, n, t이 5개의 글자는 반드시 필요하다.5이상의 k가 주어지면 일단 k-5에 대해서만 보면 되고, 주어진 단어들은 미리 비교하기 편하게 앞, 뒤 "anta"와 "tica"를 빼버리자.
이렇게 되면 알파벳 소문자 숫자는 최대 26이었는데 a, c, i, n, t 5 글자를 빼면 21개의 글자 중에서만 고르면 된다. k글자의 가능한 모든 경우의 수는 최대 21 C (k-5) 가 될 것이다.
시간 제한안에는 충분히 들어올 수 있을 것 같긴하다.
근데 21 C (k-5)의 경우의 수를 구현하는 것이 어려워보인다... 음 일단 문제 분류를 한 번 봐야겠다. 헉 보니까 문자열 처리, 시뮬레이션, 부르트포스... 내가 생각한 방식이 맞을 수도 있겠다.
일단 넘기고 다른 문제를 살펴봐야겟다.
2016년 9월 27일 화요일
BOJ 11003 최소값 찾기
이 문제는 처음에는 segment tree를 이용해야 하는 건가 생각했는데, 문제 분류를 보니 sliding window라고 되어있었고 그 걸 보고 나서 좀 감탄을 했다.
L이 정해져있기 때문에 L만큼의 window를 옆으로 이동해나가면서 최소값을 새로 나오는 수와 비교하면서 갱신하고 출력하면 될 것 같아보인다. 왜 sliding window를 생각 못했을까...
그리고 slack에서 본 것인데, 이렇게 sliding window를 쓸 수 있는 것은 L이 고정되어 있기 때문인 것 같다.
출처 : Baekjoon Online Judge Slack
그리고 입력이 500만 개이고, 이 정도 입력으로 입력만으로 1초 이상이 걸린다는 것도 알았다. 예전에 k번째 수 였나...? 그 문제도 입력이 500만이라 입력 시간때문에 nlogn으로는 힘들었던 것 같다.
일단 이 문제도 풀어봐야겠다.
음 풀려고 하니까 문제점이 드러났다. 이게 최소값 정보만 가지고 있고 만약 그 최소값이 그 구간에서 맨 처음 값이라면 window를 한 칸 움직이면 이제 그 구간에서의 최소값이 무엇인지 모른다...
일단 질문 게시판을 참조해보기로 했다. priority_queue를 이용한다는 정보...
그리고 검색으로 블로그 등을 찾아보니 min heap을 이용하는데 deque를 이용했단 글도 보이고... nlogn으로 푸는 것 같다.
그럼 한 번 segment tree나 fenwick tree를 이용해볼까... fenwick tree로 최소값을 구하는 것도 본 것 같은데 한 번 찾아봐야겠다. 일단 나중에 풀어야겠다.
L이 정해져있기 때문에 L만큼의 window를 옆으로 이동해나가면서 최소값을 새로 나오는 수와 비교하면서 갱신하고 출력하면 될 것 같아보인다. 왜 sliding window를 생각 못했을까...
그리고 slack에서 본 것인데, 이렇게 sliding window를 쓸 수 있는 것은 L이 고정되어 있기 때문인 것 같다.
출처 : Baekjoon Online Judge Slack
그리고 입력이 500만 개이고, 이 정도 입력으로 입력만으로 1초 이상이 걸린다는 것도 알았다. 예전에 k번째 수 였나...? 그 문제도 입력이 500만이라 입력 시간때문에 nlogn으로는 힘들었던 것 같다.
일단 이 문제도 풀어봐야겠다.
음 풀려고 하니까 문제점이 드러났다. 이게 최소값 정보만 가지고 있고 만약 그 최소값이 그 구간에서 맨 처음 값이라면 window를 한 칸 움직이면 이제 그 구간에서의 최소값이 무엇인지 모른다...
일단 질문 게시판을 참조해보기로 했다. priority_queue를 이용한다는 정보...
그리고 검색으로 블로그 등을 찾아보니 min heap을 이용하는데 deque를 이용했단 글도 보이고... nlogn으로 푸는 것 같다.
그럼 한 번 segment tree나 fenwick tree를 이용해볼까... fenwick tree로 최소값을 구하는 것도 본 것 같은데 한 번 찾아봐야겠다. 일단 나중에 풀어야겠다.
피드 구독하기:
글 (Atom)