게임 개발 일지

25635번: 자유 이용권 문제 풀이 result = (arr_sum - arr_max + 1

1033번: 칵테일 문제 요약칵테일 재료 n개를 받아 n-1개 만큼의칵테일 재료 a와 b 그리고 a와 b가 이루는 비율의 분모 분자 p q가 각각 준다.이를 통해 칵테일 재료의 원 재료 질량을 출력하면 된다.풀이 아이디어문제에서 주어지는 변수들의 값의 범위가 10보다 작은 자연수이기 때문에 10^10일지라도 long long을 초과하지 않는다.모든 재료의 값은 자연수이고 필요한 질량의 최소값이 필요함으로 가능하다면 유클리드를 호제법을 사용하여소수로 계산하면 된다. 각 재료들은 그래프를 통해 연결되었다고 볼 수 있기 때문에 0번째 인덱스를 기준으로 완전탐색해서0번째에 대한 1,2,,,N-1번째의 비율에 대한 분수를 계산한다음 각 분수의 분모들의 최대공배수 만큼 곱해준다면값을 구할 수 있다. 최적화 하기모든..

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가 되는 경우에  해당 지점을 수정했을 때 좌우 괄호의 균형이 맞는 다는 것을 알 수 있다.일단 이 지점에 대해 구해야 한다. 그러나 중요한 건 좌우 갯수..