Hokusai

[문제 설명] 연인 코니와 브라운은 광활한 들판에서 '나 잡아 봐라' 게임을 한다. 이 게임 은 브라운이 코니를 잡거나 코니가 너무 멀리 달아나면 끝난다. 게임이 끝나 는데 걸리는 최소 시간을 구하시오. [조건] 코니는 처음 위치에서 1초 후 1만큼 움직이고, 이 후에는 가속이 붙어 매 초 마다 이전 이동 거리 + 1 만큼 움직인다. 즉, 시간에 따른 코니의 위치는 C, C + 1, C + 3, C + 6, ...이다. 브라운은 현재 위치 B에서 다음 순간 B - 1, B + 1, 2 * B 중 하나로 이동할 수 있다. 코니와 브라운의 위치 x는 0 브라운의 위치: 2, 3, 6, 12, 13, 26, ... 브라운은 코니를 5초 만에 잡을 수 있다. =============================..

[문제]기존 배열(test)에서 test2 배열 순서대로 피자를 먹는 방법의 이동거리가 최소인 값 찾기.test배열을 원판이라 생각하고 진행. =======================================================================[Idea]Recursion(재귀)를 통해서 완성할 수 있다. 우측으로 가는 방향(+)과 좌측으로 가는 방향(-)를 동시에 진행해서 dfs를 2개로 돌린다.그렇게 깊이 들어가면서 값이 최소인 것을 찾는 방법이다. 완벽한 풀이인지는 모르겠지만 이런 방법으로 풀면 되겠다는 생각에 글을 쓴다. [Codes]

[문제]1부터 N까지의 수 중 C개를 고르는 문제1) 순서가 상관있는 경우(중복 有) - Code 12) 순서가 상관없는 경우(중복 無) - Code 2 =======================================================================[Idea]Recursion(재귀)를 통해서 완성할 수 있다. 기존 수를 가지고 있는 arr 배열, 해당 node를 방문했는지 확인하는 visited배열, 그리고 완성된 배열을 집어넣는 str배열이 있다. 재귀를 통해서 방문한 노드는 dfs를 하지않고 가는 식으로 진행한다. [Codes]기본 main은 동일하다 . : 순서 상관 有 : 순서 상관 無 이러한 경우는 다양한 문제에서 적용이 가능하다. 예를들어 몇개의 공을 뽑아 연산..

Programmers 문제 - 소수의 합 [시간제한]모든 테스트 케이스를 합쳐 1초[메모리제한] 512MB[문제]2부터 N까지의 모든 소수의 합을 구하세요. N이 7이라면 {2,3,5,7} = 17을 출력 하시면 됩니다.N의 범위는 2이상 10,000,000이하 입니다. 효율성 테스트의 모든 시간 제한은 1초입니다. =======================================================================[Idea]방법 1) O(n^2)로 다 돌려서 확인하는 경우: 기존의 소수를 구하는 방법이다. 이 방법은 n^2으로 시간복잡도가 안좋다. 효율성 4개 다 틀림방법 2) O(n^2)로 다 돌려서 확인하는 경우21과 똑같은 원리이지만 시간을 줄이기 위해 이중for문 내 ..

[시간제한] 50 개의 테스트 케이스를 합쳐 1초.[메모리제한] 512MB[문제]N장의 카드가 놓여져 있는데, 이를 순서대로 선택하여 단어를 만들려고 한다. 단어를 만들 때는 선택한 카드를 이미 선택된 카드들의 제일 왼쪽 또는 오른쪽에만 위치시킬 수 있다.예를 들어 3장의 카드가 E, O, T 순으로 놓여져 있다고 하자. 순서대로 선택하므로 E를 먼저 선택하고 두번째 O를 E의 왼쪽에 붙일 경우 OE, E의 오른쪽에 붙일 경우 EO가 된다. 세번째 T를 OE의 왼쪽에 붙일 경우 TOE, OE의 오른쪽에 붙일 경우 OET, EO의 왼쪽에 붙일 경우 TEO, EO의 오른쪽에 붙일 경우 EOT라는 단어를 만들 수 있다. 3장의 카드로 만들어진 단어 TOE, OET, TEO, EOT 중에서 사전순으로 가장 느린..

[시간제한]10 개의 테스트 케이스를 합쳐 1초[메모리제한] 512MB[문제] 절대로 탈출할 수 없다고 알려진 감옥에서 죄수들이 탈출했다. 이들은 감옥 근처에 세워져 있던 차를 훔쳐서 도주하고 있으며, 총 N대의 차량을 이용하고 있다. 이 차량들에 대한 정보라고는 각각의 차량의 색상 뿐이다. 즉, 빨간 차는 몇 대, 파란 차는 몇 대, … 와 같다.죄수를 추적하던 경찰은 다음과 같은 가정을 하게 되었다.죄수들은 차량을 이용하여 수도로 이동할 것이다. 그런데, 감옥에서 수도로 이동하려면 반드시 특정한 톨게이트를 지나야 한다.이들은 도로 정보를 잘 모르기 때문에, 사이에 다른 차가 끼면 뒤의 차는 앞 차를 놓치고 길을 잃게 된다. 따라서 반드시 이들은 한 줄로 붙어서 이동할 것이다. 죄수들의 차량간 순서는 ..