https://www.acmicpc.net/problem/1011 시작점 x부터 도착점 y까지 이동하는 문제. 이동 횟수를 구해야 한다. 이동 속도는 1부터 시작하고, 한 번 이동할 때마다 ±1씩 증감한다. 마지막 지점에 들어오는 속도는 반드시 1이 되어야 한다는 조건이 있다. 즉, 속도는 1씩 증가하여 중간 지점에서 최대치에 도달한 후 서서히 감소하여 다시 1로 돌아온다. 규칙을 찾아보기 위해 표로 정리해 보았다. 두 지점 사이의 거리 최적의 속도 변화 1 1 2 11 3 111 4 121 5 1211 6 1221 7 11221 8 12221 9 12321 10 112321 11 122321 12 123321 ... ... 1번 이동 : 1항부터 2번 이동 : 2항부터 3번 이동 : 3항부터 4번 이동..
알고리즘
https://www.acmicpc.net/problem/1463 정수 X를 1로 만드는 연산의 최소 횟수를 구하는 문제이다. ① 3으로 나누기 ② 2로 나누기 ③ 1 빼기 1로 만드는 가장 빠른 것은 1번 연산이다. 그 다음은 2로 나누기, 1 빼기 순이 될 것이다. 숫자 1은 이미 1이므로 연산이 필요 없고 2와 3은 1번의 연산을 해야 한다. int d[1000001] = { 0, 0, 1, 1, }; 여기서 d[X]은 X을 나누는 최소 횟수이다. 배열의 인덱스는 X의 최대값인 106 + 1 까지이며 0~3을 1로 만드는 최소 횟수를 초기화했다. 3까진 이미 정했으니 4부터 규칙을 차근히 생각해보면 숫자 4를 만드는 방법 : 2 * 2, 3 + 1 숫자 5를 만드는 방법 : 4 + 1 숫자 6를 만..
https://www.acmicpc.net/problem/6588https://www.acmicpc.net/problem/9020 유사한 두 문제에 관한 풀이이다. 소수를 구하는 방법은 여러가지가 있다. 가장 간단한 방법으로는 임의의 숫자 n에 대하여 [1, n-1]의 범위에서 일일이 나누어보는 방법이 있겠지만 시간의 제약이 있는 알고리즘 문제에서는 사용할 수 없다. 소수를 구하는 유명한 알고리즘으로 '에라토스테네스의 체'가 있는데, 이 문제에서도 힌트로 주어져 있다. 소스 코드로 적용하기는 쉽다. 우선 bool 또는 정수형 배열 하나를 만든다. 나는 간단하게 c라고 정의했다. 우선 모든 값을 0으로 초기화하고, 숫자 n이 소수라면 c[n]의 값은 1이 된다. for(int i = 4; i
