열심히해보겠씁니다

자기만 재밌는 게임을 한다고 한다... 직사각형 보드에서 동전이 구멍에 빠지거나 보드 바깥으로 나가지 않는 선에서 게임을 오래 즐기고 싶다고 한다. 최대 몇 번 움직이는지는 손으로 구해보면 쉽다. 보드의 크기는 최대 50x50이고 각 칸에 적혀있는 숫자는 1~9이며 구멍일 수 있다. 몇 가지 점을 빠르게 알 수 있다. 1. 내가 갈 수 있는 칸에 나와 똑같은 숫자가 있으면 무한번 움직일 수 있다. 1-1. 그러므로 무한번이 아닌 경우는 도착하는 숫자가 모두 다르다. 2. 한 번이라도 지나온 칸에 다시 도착한다면 무한번 움직일 수 있다. 2-2. 다시 도착하지 않는다면 반드시 게임은 종료되고, 따라서 그 칸에서 최대한 움직일 수 있는 횟수는 정해져 있다. 즉 무한번 움직일 수 있는지 판단은 두 가지로 할 ..

지렁이가 이동하는 총스칼라가 최소가 되게 하면 됩니다. 벡터의 크기는 편의상 루트를 없앤 x^2 + y^2로 계산합니다. 지렁이는 최대 20마리까지 존재하며 짝수입니다. 모든 좌표값은 -10만 c 벡터를 더하면 b 벡터이니, c 벡터는 b 벡터 - a 벡터입니다. 고로 두 점 사이의 거리는 (4,1) - (1,3) = (3, -2)이고, (0,0)과 (3,-2)의 거리는 3^2 + (-2)^2 = 13입니다. 다만, 다른 지렁이 벡터들도 모두 합한 후 거리를 구해주어야 합니다. 여기서 가장 가까운 지렁이로 가야 한다는 조건 때문에 가장 가까운 지렁이를 찾는 과정을 넣으시면 시간초과가 날 확률이 높습니다. 벡터의 합을 구하는 것이고, 벡터의 합은 완전히 더하기 빼기로만 이루어져 있으므로 자연스럽게 결합법칙..

우리에게 익숙한 사다리 타기 문제이다. 모든 번호가 자기 자신을 뽑도록 만들고 싶다. 주어진 사다리에다가 최대 3개의 가로줄을 그어서 자기 자신을 뽑도록 만들면 성공이지만 3개를 초과해야 할 경우엔 실패로 처리한다. 물론 주어진 사다리가 그대로 성공한 경우도 있으므로 0개도 답이 될 수 있다. 접근 방식은 다음과 같다. 1. 0개부터 최대 3개까지 사다리를 임의로 긋는다. 2. 자기 자신을 가리키는지 확인한다. 3. 1-2를 반복하다가 성공하면 그은 횟수, 실패하면 -1를 리턴한다. 해결 방식으로 생각한 것은 다음과 같다. 1. 모든 사다리는 자기 자신으로 돌아와야하기 때문에 가로줄은 세로줄 하나 당 짝수 개가 필요하다. -> 당연한 얘기지만 홀수가 없는 경우도 케이스로 들어오므로 알고리즘에 반영하기 힘..

홀수 중독자 호석이 이야기다. 주어진 10^9 이하의 숫자를 쪼개고 쪼개서 홀수를 가장 많이 보고 싶다고 한다. 문제의 조건은 다음과 같다. 1. 마지막 한 자리만 남기 전까지의 과정에서 가장 홀수를 많이 보는 경우와 적게 보는 경우를 구한다. 2. 시작 숫자부터 중간과정의 숫자에서 나타나는 모든 홀수를 세지만 마지막 한 자리만 남았을 때는 세지 않는다. 3. 두 자리 숫자는 두 개로 나누면 되지만, 수가 세 자리 이상일 경우 임의의 자리에서 '알아서' 잘라서 3종류의 숫자로 만들어서 다 더해서 다음 숫자를 구한다. 문제의 접근 방식 및 해결방식은 다음과 같다. 0. 완전탐색 1. 자릿수마다 처리하는 방식을 다르게 한다. 2. 세 자리가 넘어가는 수를 다룰 때는 자를 위치를 두 곳 정하고 다음 숫자를 구..

CCTV 의 위치와 종류가 주어져있고, 방의 구조가 주어진다. CCTV로 감시할 수 있는 영역을 최대한으로 늘리는 것이 목표다. 문제의 조건은 다음과 같다. 1. 감시할 수 있는 부분을 최대한 늘릴 것 2. CCTV는 종류별로 감시할 수 있는 영역이 다르고, 방향 또한 바뀔 수 있다. 가령 1번은 오른쪽을 가리키고 있지만 돌려서 설치하면 위쪽을 감시하게 만들 수 있다. 문제의 접근 방식은 다음과 같다. 1. 완전탐색 문제의 해결방식은 다음과 같다. 1. CCTV를 돌려서 보는 방향을 바꿀 수 있다면 돌리면서 감시할 수 있는 영역을 확인한다. 2. 다른 CCTV에 대해서 1번을 수행한다. 방의 크기가 최대 8x8 이고 CCTV가 최대 8이므로 최악의 경우에도 6천가지 정도의 경우의 수를 탐색하면 된다. 고..

내 친구 호석이가 애벌레가 되어버린 문제이다. 호석이는 한 번 시작하면 특정 조건을 만족하기 전까지는 연속해서 먹이를 먹는다. 탙피 에너지를 최대한으로 축적하고 싶은데, 얼마나 축적할 수 있는지를 계산해보자. 문제의 조건은 다음과 같다. 1. 탈피 에너지를 최대한으로 쌓을 것 2. 먹이를 하나 먹으면 조건을 만족할 때까지 계속 먹을 것 문제의 접근 방식은 다음과 같다. 1. 먹이를 먹을 수도 안먹을 수도 있기 때문에 단순 루프로 접근하려면 케이스를 여러개 고민해줘야한다. 2. 애벌레의 다음 행동은 지난 행동에게 영향을 받는다. (직전 먹이를 먹었다 -> 조건 만족하면 멈추고 만족못하면 계속 먹어야함, 직전 먹이를 먹지 않았다 -> 이번 먹이를 먹을수도 안먹을수도 있다.) 3. 당장 최대한으로 만들 수 있..

백준 회사에서 축구대회를 한다. 팀원을 짜고 싶은데 시너지가 잘맞는 팀원이 있고 아닌 팀원들이 있어서 잘 짜야한다. 물론 재미있게 플레이하기 위해 전체적인 실력이 비슷해야한다. (20명인거보니 골키퍼는 고려안하나봐) 문제의 조건은 다음과 같다. 1. 두 팀의 능력치가 가장 비슷한 경우를 찾기 2. 두 팀의 인원은 같다.(N은 짝수) 3. 한 명이 특정 팀에 들어갈 경우 그 팀에 있는 모든 사람들과의 시너지를 계산해야한다. 전체코드 #include #include int N; int Min = 987654321; int Map[21][21]; int used[21]; int abs(int x) { if (x < 0) return -x; return x; } //시너지 계산 int check() { int ..

아주아주 간단한 문제.. 인 줄 알았는데 2시간은 쓴 것 같다. 문제 자체는 아주 간단하다. 트리를 만들고 자르라는걸 자르고 leaf의 개수를 세면 된다. 틀린 지점은 3곳이다. 1. 0%에서 틀렸다면, 배열이 항상 0번 인덱스가 Root로 나오는 것은 아니라는 것을 파악하고 다시 코드를 짜야한다. 혹은 루트를 잘랐을 경우를 고려하지 않았을 수 있다. 다음 예시를 참고해보자 3 1 -1 1 0 정답) 1 3 -1 0 0 0 정답) 0 2. 77%에서 틀렸다면, 자식이 2개라고 생각하고 구현했을 가능성이 높다. 5 -1 0 0 0 0 3 정답) 3 3. 99%에서 틀렸다면 Root만 남았을 경우에 틀렸을 가능성이 높다. 5 -1 0 1 2 3 1 정답) 1 고생한 점은 다음과 같다. 1. 그림에 낚여서 자..

문제를 이해하기에 앞서 2048 (play2048.co) 를 한 번 해보면 좋다. 설명보다 훨씬 직관적으로 이해하기 편하기 때문. Easy 버전 답게 게임과는 다른 점이 있다. 1. 숫자는 초기 상태에서 추가되지 않는다. 2. 만들 수 있는 최대값만 알면 된다. 숫자가 추가되지 않고 움직이는 횟수가 적기 때문에 쉽다고 하는 것 같은데, 충분히 머리를 써야한다. 접근 방식은 다음과 같다. 1. 맵이 비교적 작고(20*20) 최대 5회까지만 움직이기 때문에 기껏해야 100만번의 경우를 완전탐색하면 된다. 해결 방식은 다음과 같다. 1. 현 상태에서 밀 수 있는 경우(좌우상하 네 가지) 중 하나를 수행한다.(DFS) 2. 최댓값을 갱신할 수 있는지 확인하고, 1번을 반복한다. 3. 5번 바꿀 경우 종료한다. ..

바다와 섬이 그려져있는 지도에 다리를 만들되, 다리를 최소한의 길이로 만들고 싶다. 조건은 다음과 같다. 1. 다리의 길이는 1보다 길어야한다. 2. 섬이 모두 연결되어야 한다. (연결 안될 경우 -1출력) 3. 다리는 일직선으로만 만들 수 있다. 4. 다리 양끝에 다리 방향으로 섬이 연결되어야 한다.(옆 방향에 붙는 것 안됨) 5. 다리는 교차할 수 있지만, 길이는 중복해서 센다. 가령 길이 3인 도로가 + 형태로 겹쳐있어도 길이는 6이다. 접근 방식은 다음과 같다. 1. 섬마다 번호를 매긴다. 2. 섬마다 만들 수 있는 다리를 모두 만들어 보고, 연결할 수 있는 섬과 그 때의 다리의 길이를 저장한다. 3. 최소 값으로 섬들을 연결시킨다. 4. 섬들이 모두 연결되어 있는지를 확인한다. 문제를 풀면서 고..