게임 개발 일지

12982번: 공 포장하기 2문제 요약k개의 종류를 가진 공이 존재한다.종류마다 공의 갯수는 각각 다르다.이 공들을 박스에 담을 것이며 박스는 다음 두가지 방식으로 최대 k개의 공을 담을 수 있다.1. 박스 안의 모든 공의 종류가 다르다.2. 박스 안의 모든 공의 종류가 같다. 최소한의 박스로 공을 전부 담아라. 풀이 아이디어 먼저 입력 받을 때 같은 종류로 k개를 상자에 담을 수 있다면, 담고 본다.즉 k개로 나눈 몫 만큼을 결과에 미리 추가해 놓고, k개로 나눈 나머지 값을 입력값으로 사용한다. 그 다음 입력값을 오름차순으로 정렬한 후순회하며 i번째 까지 1번으로 담는 방법 (오름차순 정렬임으로 i번째 입력값이 박스의 갯수다.) +i+1번째 부터 2번으로 담는 방법( k - 1 - i 가 박스의 갯수..

1242번: 소풍문제 요약3 6 9 게임과 비슷하게 숫자를 돌리면서k번째 숫자 마다 지목당한 사람을 제외시킨다.처음 m번째 있던 사람이 몇번째에 제외되는지를 출력한다. 풀이 아이디어 직관적인 문제이긴 하나 n이 500만 임으로 단순 구현으로 풀기에는 O(N^2)이 소모된다.따라서 수학식을 통해 연산량을 줄이는 방법을 채택했다. 또한 처음 시작 지점을 임의로 조정하여k > m 일때 시작 지점  =  -mk  동호가 항상 남아있는 사람들 중 가장 끝자리에 있겠끔 만들 수 있다. (끝자리로 남길 경우 한 싸이클 계산이 편해진다. )  3가지 조건을 만들어서 k를 추가해도 m 보다 작을 때- 나누기 연산으로 제외할 수 있는 인원만큼 결과값 추가- 추가한 인원 만큼 전체 인원 수 제거- 시작 지점 갱신+ 만약 추..

14586번: 도미노 (Small)  풀이 아이디어 모든 도미노를 순회하면서i번째 도미노를 왼쪽으로 넘어트렸을 때  연쇄 반응이 완료되는 지점에서 -1인 odp[i] = min (dp[i] , dp[o] + 1)  i번째 도미노를 오른쪽으로 넘어트렸을 때 연쇄 반응이 완료되는 지점인 kdp[k] = min(dp[i-1] + 1 , dp[k])를 dp로 계산해서 n-1 지점을 출력하면 된다. n이 300임으로 연쇄반응이 끊기는 지점을 순회해서 돌더라도시간복잡도 O(n^2)안에 풀 수 있다.   시행착오 처음에는 유니온파인드와 그리디를 이용하여 가장 많이 넘어트릴 수 있는 도미노를 구해서 풀리는가 생각해봤는데 도미노가1 1 1 1 10 5 4 3 2 1 이런식으로 배치된다면 해를 내지 못하게 된다.  최적화..

26599번: 용 조련사 룰루풀이 아이디어 각각의 용이 장소내에 다른 모든 용에 대하여 m보다 크지 않도록 하여 다른 장소로 옮기는 문제이다. 이 문제의 풀이법은 애드혹으로 문제를 푸는 핵심 포인트는시작장소와 도착장소에 서로를 억제할 수 있는 가장 큰 두 쌍의 용을 두는 것이 중요하다. 1, 2번째로 큰 용을 한 쌍, 3, 4번째로 큰 용을 한 쌍으로 묶는다. 1, 2번 째 용을 옮긴다음3, 4번째 용을 제외한 모든 용을 옮기고 나서 남아있던 3, 4번째 용을 옮기면 된다. 주의할 점은 위 4마리의 용들은 인접한 용들간의 차이가 m이하 여야 된다.그렇지 않다면, 용을 옮기는 과정에서 학살이 일어나게 된다. 따라서 4마리 이상이 주어진다면, 정렬 후 1~4번째 큰 용들의 차이가 m이하로 연속적인지 판단 후..

16118번: 달빛 여우 풀이 아이디어 다익스트라 문제로늑대는 한번은 2배 빠른 속도 한번은 2배 느린속도로 이동여우는 정상적인 속도로 이동하며이때 여우가 늑대보다 빠르게 도착 할 수 있는 지점이 몇개인가를 찾는 문제이다. 가중치가 거리이기 때문에 2배 빠른 속도라는건 가중치를 2배로 나눈다는 것과 동치이다. 따라서 여우와 늑대가 시작지점에서 끝지점까지 갈 수 있는 모든 거리를 구한다음서로를 비교하며 여우가 더 작은 값을 갖고 있는 지점을 카운트하면된다. 여우는 정석적인 다익스트라로 구하면 되고늑대는 다익스트라를 조금 변형하여 이동횟수를 1과 0으로 기록하여2배 빨라야 할 때 와 2배 느려야 할 때를 계산해서 가중치를 계산하고이동횟수를 스위치 시킨다음 다시 큐에 넣어서 계산하면된다. 그리고 이동횟수에 따..

13415번: 정렬 게임풀이 아이디어 구현을 통해서 입력을 받을때마다 정렬을 하게 된다면  O(N*NLog(N))이 걸리게 된다.N이 10만이기 때문에 구현으로만 풀면 시간초과를 받게 된다. 이 문제의 핵심은 정렬하는 대상이 반드시 1부터 시작 한다는 것과이전에 실행했던 정렬보다 같거나 큰 범위로 정렬하게 된다면 이전에 실행했던 정렬이 아무런 의미가 없다는 점이다. 먼저 후자를 살펴보자면 인덱스 1 ~ 3 을 정렬해봤자 이후 인덱스 1 ~ 4를 정렬하면 1 ~ 3 정렬은 아무런 의미가 없다는 점이다.즉 이 문제에서 결과에 유의미한 영향을 끼치는 정렬은정렬 입력값을 받았을 때가장 큰 수 부터 내림차순으로 정렬된 정렬값만이 결과에 영향을 끼친다. 만약숫자를 1 2 3 4 5 6 7 8 9 10으로 받고 정렬..

1797번: 균형잡힌 줄서기풀이 아이디어일렬로 세웠을 때 성별의 수가 같은 가장 긴 그룹을 구하는 문제이다. 데이터의 범위가 적으면서 이 문제와 결이 비슷한 문제가 많은데데이터의 범위가 적을 경우한 방향 누적합을 통해 시작 지점과 끝 부분의 누적합을 빼서 성별의 균형을 유지하는 식으로 브루트포스를 진행한다면O(n^2)으로 해결할 수 있다. 그러나 해당 문제는 n이 100만임으로 브루트포스를 진행하면 시간오버가 나게 된다. 이 문제를 푸는데 핵심은문제에서 요구하는 것이 가장 긴 연속적인 선분이라는 것과map을 통한 계산이다. 가장 긴 연속적인 선분이라는 것은 전체에서 조건에 부합하는 양쪽 선분을 제외한 것과 동치라는 것이다.위와 같이 생각한다면 우리가 구하려는 것은 전체에서 성별의 균형을 이루도록 하는 좌..

5875번: 오타  풀이 아이디어어떻게 풀어야 되나 고민했지만, 아이디어를 떠올리지 못해누적합이라는 태그를 봐버렸고, 누적합을 사용 할 수 있었다. 먼저 누적합이란 것을 알고나면괄호를 수정했을 때 경우의수가 1개이상 나오는 데이터들은누적합이 2나 혹은 -2라는 것을 알 수 있다.(괄호의 갯수가 2개 차이나야 하니) 일단 이 이외에 모든 경우는 제외시키자. 그 다음누적합을 통해 양쪽방향으로 각각 한번씩 누적합을 구해괄호 갯수에 대한 갯수를 구한다. 그렇게하면특정 지점까지의 좌측 방향 누적합과 우측 방향 누적합을 알 수 있고괄호에 따라서 이 차이가 +- 2가 되는 경우에  해당 지점을 수정했을 때 좌우 괄호의 균형이 맞는 다는 것을 알 수 있다.일단 이 지점에 대해 구해야 한다. 그러나 중요한 건 좌우 갯수..

31864번: 눈송이 탕후루 만들기       풀이 아이디어0,0에서 끝점까지의 선을 기준으로 하기 때문에모든 탕후루는 반드시 기울기가 같은 끝점에만 꽂힐 수 있다. 따라서 끝점을 기준으로 순회하며0,0과 끝점사이의 기울기가 같은 탕후루가 몇개인지를 확인하면 되는 문제이다. 브루트포스로 풀 경우 최악의 경우 모든 눈송이와 끝점이 같은 선상에 있는 경우가 존재하며따라서 O(n*m)이 나올 수 있다.  그렇기 때문에 최적화 방법으로 이분탐색을 추가했다. 기울기를 키값 하는 배열을 만든 다음x좌표를 벨류 값으로 넣고 정렬 시켰다. 그 다음 입력 받는 좌표로 기울기를 구한다음 그 기울기에 해당하는 배열에서 x값을 토대로 이분탐색해서갯수를 구했다.x나 y좌표가 0일때도 있는데 이건 예외처리해서 다른 배열에 담아서..

16957번: 체스판 위의 공시간 제한메모리 제한제출정답맞힌 사람정답 비율2 초512 MB212282359838.309%문제크기가 R×C인 체스판이 있고, 체스판의 각 칸에는 정수가 하나씩 적혀있다. 체스판에 적혀있는 정수는 모두 서로 다르다.체스판의 각 칸 위에 공을 하나씩 놓는다. 이제 공은 다음과 같은 규칙에 의해서 자동으로 움직인다.인접한 8방향 (가로, 세로, 대각선)에 적힌 모든 정수가 현재 칸에 적힌 수보다 크면 이동을 멈춘다.그 외의 경우에는 가장 작은 정수가 있는 칸으로 공이 이동한다.공의 크기는 매우 작아서, 체스판의 한 칸 위에 여러 개의 공이 있을 수 있다. 체스판의 상태가 주어진다. 공이 더 이상 움직이지 않을 때, 각 칸에 공이 몇 개 있는지 구해보자.입력첫째 줄에 체스판의 크기..