1069 집으로

2차원 그래프에서 0,0으로 다음의 두 조건을 통해 가려 할때의 최솟값을 찾는 문제이다.
1. 1초에 1의 속도로 걷는다.
2. t초에 d 만큼 점프한다. (직선으로만 도중에 멈추기 안됨)

이 문제는 두 점을 잇는 직선으로만 생각하면 안된다. 왜냐하면 각도를 조금 틀어서 한 번 더 점프하는것이 이득인 경우가 있기 때문이다.
내가 본 가장 효과적인 방법은
점프 가능한 거리만큼은 점프를 하고 나머지 1번을 여러 케이스로 나눠서 최솟값을 찾는것이다. 보면 구현은 쉽지만 각 케이스가 실제 그런지에 대한 고민이 필요하다.

나는 결국 생각하지 못하고 다른 사람이 올린 소스를 중심으로 풀었다.
반성이 필요한 순간이다..

소스

2417 정수 제곱근

정수의 제곱근을 찾아 올림하는 문제이다.

간단하게 sqrt 함수와 ceil 함수를 이용했다. 이렇게 하지 않고 반복문을 통해 하는 방법도 가능하다.

소스

Pollard's Rho

어떤 수의 인수(factor)를 찾아내는 알고리즘이다.
특히 큰 수의 인수를 찾을 때 유용하고, 메모리를 거의 차지하지 않으며 O(n^(1/4))의 시간복잡도를 보인다고 한다.

gcd 와 x^2+-a (1,-1) 을 이용하는데, 정확한 수학적 원리는 모르겠다.
실제 테스트를 해봤는데, 약수를 전부 찾아내는건 아니지만 큰 수인데 인수가 2~3개 밖에 안되는 경우도 빠르게 찾아냈다.

참고

소스

modular exponentiation

a^b mod c 를 구하는 알고리즘이다.
단순하게 a^b를 하고 c로 나머지를 하면 프로그래밍에서 오버플로우가 발생하기 때문에,
중간과정에 modular 연산을 해줌으로써 오버플로우를 방지한다.
물론 이렇게 해도 결과가 달라지는 일은 없다고 한다.

b승을 단순히 a를 b번 곱하는 식으로 하게 되면 O(b)의 시간복잡도가 생기는데,
이것은 빠른 방법이 아니다.
이에 관련된 알고리즘엔 여러가지가 있는데,
이 중 하나의 방법으로 2씩 나눠가는 방법이 있다.
a^b = (a^2)^(b/2) 라는것을 이용하여 O(log2(b)) 의 시간복잡도 안에 해결 가능하다.

소스

2986 파스칼

파스칼 코드로 되어있는 프로그램의 결과를 출력하는 문제이다.
파스칼 코드의 의미는 N-1부터 1까지 반복하면서, N과 나누어떨어지는 수가 발견되면 그 숫자가 나올때까지의 반복횟수를 출력하는것이다.

사실 이 소스를 그대로 C로 구현해도 정답이 맞아야 하지만, 얄밉게도 TLE가 발생하는 구조로 되어있다.

따라서 이 문제는 N보다 작으면서 N과 나누어떨어지는 수의 최댓값을 찾아야 하는데,
이는 N을 N의 가장 작은 약수로 나눈값과 같다.

따라서 N의 가장 작은 약수를 찾으면 되는데, 이것은 O(root(N))의 시간복잡도를 가지게 찾을 수 있다.

소스

5054 주차의 신

가게가 일렬로 되어 있을 때, 모든 가게를 들른다고 가정하면 차까지 돌아오는 거리가 가장 짧은 경우를 출력하는 문제이다.

얼핏보면 주차의 위치를 선정해야하는 것처럼 보인다. 하지만 사실은 어느곳에 주차를 하던 상관이 없다. 왜냐하면 차까지 돌아오는 거리가 가장 짧으려면, 주차된 위치에서 오른쪽 끝 가게 까지 일직선으로 들렀다가 돌아오고, 다시 왼쪽 끝 가게 까지 일직선으로 들렀다가 돌아와야 하는데, 그 거리는 왼쪽 끝에서 오른쪽 끝까지의 거리의 2배가 되기 때문이다. 따라서 어디다 주차를 하던, 왼쪽 끝과 오른쪽 끝 사이의 거리는 일정하기 때문에, 답은 이 값의 2배를 한 것이다.

소스

2607 비슷한 단어

첫번째 단어와 비슷한 단어의 갯수를 구하는 문제이다.
비슷한 단어란, 처음단어와 주어진 단어가 사용된 문자, 문자의 갯수가 같거나, 문자를 하나 더하거나 빼주거나 한 문자를 다른 문자로 바꿔 주는 작업을 통해 앞의 조건을 만족한다면 비슷한 단어라고 한다.

이 문제를 푸는 방법은, 처음 단어의 사용된 문자와 횟수를 담는 배열을 만들어 주고, 주어지는 단어의 배열도 만들어 준 다음, 둘을 서로 비교하여 횟수가 다른것을 찾아야 한다. 횟수가 다른것에 여러 패턴이 있는데, 그것들을 이용해서 둘이 같은단어인지, 한번의 작업을 통해야 하는지, 둘이 다른단어 인지를 밝혀내면 된다.

소스