굥굥

해설 어려운 문제는 아니어서 재귀로 풀어봤다가 피보나치를 이용해서 풀었다. 재귀는 시간초과가 7번부터 난다. 피보나치를 이용한 이유는 다음과 같다. n = 1, result = 1 n = 2, result = 2 n = 3, result = 3 n = 4, result = 5 n = 5, result = 8 n = 6, result = 13 n = 7, result = 21 n = 8, result = 34 이 되므로 피보나치를 이용할 수 있다. 문제 설명 효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다. 칸이 총 4개 있을 때, 효진이는 (1칸, 1칸, 1칸, 1칸) (1칸, 2칸, 1칸) (1칸, 1칸, 2칸) (2칸, 1칸, 1칸) (2칸, 2칸) 의 5..

해설 행렬 회전에 대해 공부하다가 만나게 된 문제이다. 흥미로워서 코딩테스트 시간에 풀어보려고 점찍어뒀던 문제! 접근방법은 간단하다. 키를 회전하면서 자물쇠의 크기대로 열쇠를 비교해주면 된다. 먼저 우리가 원하는 모습은 키를 오른쪽으로 90도 회전 시킨 후 아래와 같이 적용한 모습이다. 위의 모습을 만들기 위해서는 키를 하나하나 자물쇠에 대입해보면 된다. 위의 그림처럼 빨간색이 자물쇠라면 키를 한 칸씩 이동시켜서 자물쇠와 비교해 주면 된다. 이를 구현하기 위해서는 자물쇠를 자물쇠*3 사이즈의 벡터 가운데에 넣어주는 작업또한 필요하다. 그렇게 구현해서 테스트 케이스 출력을 해보면 다음과 같이 나온다. 21,21 좌표에서 키의 모습이 아래와 같을 때 true 가 된다는 소리이다. 나는 자물쇠의 크기 *3 을..

어제 풀었던 요격 시스템과 비슷한 문제. (거의 동일하다고 봐야함ㅋㅋ) 그리디를 이용하여 문제 해결하는 방식이다. routes가 끝나는 지점을 기준으로 오름차순을 정렬해주면 문제 해결이 쉬워진다. 현재 라우터가 종료되는 시점을 벗어나면 answer를 갱신해주고 라우터의 범위를 다음번 라우터의 종료시점으로 맞춰주기만 하면 되는 문제이다. 고속도로를 이동하는 모든 차량이 고속도로를 이용하면서 단속용 카메라를 한 번은 만나도록 카메라를 설치하려고 합니다. 고속도로를 이동하는 차량의 경로 routes가 매개변수로 주어질 때, 모든 차량이 한 번은 단속용 카메라를 만나도록 하려면 최소 몇 대의 카메라를 설치해야 하는지를 return 하도록 solution 함수를 완성하세요. 제한 사항 차..

works 벡터에 들어있는 값을 최대한 균등하게 만들어 주는 것이 포인트인 문제이다. 어제 푼 문제와 비슷하게 n이 works.size() 보다 더 클 경우에 벡터의 모든 요소에 n/size 한 몫만큼을 빼주었는데 문제가 생긴다. 질문하기에 있는 반례는 다음과 같다. 위의 상황에서는 내가 생각한 접근법이 맞지 않는다... 무조건 가장 큰 원소에 접근해서 값을 빼주고 싶은데 말이다. 그래서 생각해 낸 방식이 우선순위 큐를 이용한 방식이다. 무식하게 우선순위 큐를 만들고 큐의 top에 접근해서 하나씩 빼주고 0이 아니면 다시 넣어주었다. 이렇게 하면 문제를 쉽게 풀 수 있다. n이 1,000,000 이 최대 값이라 걱정을 했으나,, 어짜피 n은 한번만 돌면 되므로 그냥 써도 시간문제는 생기지 않..

자연수 집합의 합이 s 인 값중 곱이 최대인 집합을 찾는것이 포인트이다. 최대의 집합은 집합끼리의 차가 크지 않을때 이다! 따지면 다음과 같다. s 가 2 일때 8은 4,4 9는 4,5 10은 5,5 같은 식이 된다. 만약 s가 3이라면 9는 3,3,3 10은 3,3,4 11은 3,4,4, 12는 4,4,4 ... 가 된다. 이렇게 나열하면 규칙이 보이게 된다! s를 n으로 나눈 몫을 s의 개수만큼 벡터에 넣는다. 그리고 s%n 이 0이 아닐때는 나머지를 1씩 쪼개서 벡터의 끝부분에서부터 넣어주면 된다. s 가 3이고 n이 11 일 때는 { 3, 3+1, 3+1 } 이 되는 것! 규칙을 찾으면 쉬운 풀이를 찾을 수 있다. 자연수 n 개로 이루어진 중복 집합(multi set, 편..

bfs로 풀면되겠구나~ 라고 생각이 들지만 잘 풀리지 않았던 문제.. 코너마다 cost가 다르기 때문에 경로에 대해 cost의 값을 비교해줘야해서 어렵게 느껴진다. 아래의 문제로 인해 3차원 배열을 선택해서 문제를 풀었다. 그림을 보자. -1은 이동하지 못하는 곳이다. 좌측 상단을 보면 600의 값에서 코너를 하나 만들고 아래로 내려오는 값이 1200 이다. 그런데 1200 옆에 있는 1100을 보면 1200은 1100에서 직진해서 만들어지는 값이기도 하다. 이 때에는 600에서 1200으로 코너를 하나 만들고 그 뒤 아래로 계속 직진할 수 있으므로 600->1200 이 되어야 한다. 1100 -> 1200 인 파란색 경로대로 만들면 1200 아래의 값이 1200 + 600 이 되어버려 최소..

보자마자 간단히 for문으로 풀면 당연히 시간초과가 나겠군. 이라고 생각이 든 문제였다. 보통 이런문제는 누적합으로 문제를 풀기 때문에 누적합으로 접근을 해야하는 문제임을 확신하고 질문하기 들어가보니까 역시 누적합으로 접근해야 하는 문제였다. 누적합은 많은 연산을 딱 한번만 진행하는 것. 건물을 부수고 수리하는 많은 skill 배열을 한번만 돌아서 연산해야할 수를 정해준다. 각 skill 마다 최대 1000*1000 행렬을 돌지 않아도 되는것. 가로세로의 누적합을 각각 계산해야해서 인덱스를 조절해주는게 좀 까다로웠다. 예를들어 [ 0, -2, -2, -2 ] 이렇게 데미지가 들어간다면 실제 배열은 [ 0, -2, 0, 0, 2 ] 와 같이 처리해주어야 하니 말이다. 이게 가로 누적합은 쉬운데..

어제에 이어 오늘도 이분탐색 문제다! 일단 문제를 보고 for문으로 한명씩 보내면서 탐색하는 방법을 사용해봤다. for문으로 풀면서 뭐야 레벨3 이렇게 쉬워도 돼? 라고 생각했는데 역시나 for문으로는 풀리지 않는 문제이다. 배열의 크기가 200,000 일수도 있기때문. 어제까진 이분탐색을 언제 사용해야하는지 감이 좀 잡히지 않았는데 오늘 문제를 풀고나니 좀 감이 잡힌다. 풀이 방법은 mid 값을 정해준 뒤 mid 값의 니니즈 친구들을 전부 보내보는 방법이다. 그러다 건널 수 없게되면 mid 값을 하나 낮춰서 진행하면 된다. 그러면 mid 값은 어떻게 구하는지 궁금할 수 있게된다. 일단 left는 무조건 1로 둔다. 그리고 right 값은 징검다리 돌중에 가장 큰 원소값을 가져온다. 징검다리..