알고리즘/문제풀이

[백준] 2869 - 달팽이는 올라가고 싶다.

문제 : www.acmicpc.net/problem/2869 2869번: 달팽이는 올라가고 싶다 첫째 줄에 세 정수 A, B, V가 공백으로 구분되어서 주어진다. (1 ≤ B < A ≤ V ≤ 1,000,000,000) www.acmicpc.net 문제 정답률이 약 26%로 낮은 편이다. 실수에 주의하며 어떻게 풀지 계획해보자. A = 100, B = 99, V = 200일 때, 하루에 1m씩 올라갈 수 있으므로 200일이 걸린다. 라고 하면 틀리게 된다. 정상에 올라간 후에는 미끄러지지 않는다고 했으므로, 101일 째 낮에 200m를 모두 올라간 후 이동이 끝난다. 이를 수식화해보자. 1) A - B = D 라고 하자. 2) ( V - A ) / D 는 ( V - A )미터를 올라가는데 걸리는 시간이다..

[백준] 1193 - 좌표계 도입

문제: www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net X가 주어지면 분수값을 찾아야 한다. 하지만 X를 가지고 바로 분수값을 찾기가 쉽지가 않다. 위의 표를 다음과 같은 좌표계에 대입해보자. 왼쪽 상단을 원점으로 하는 직교 좌표계이다. 그리고 분수와 분모의 합이 같은 칸끼리 선으로 이으면 위와 같이 된다. 저 직선의 방정식을 구해보자. 분수와 분모의 합이 k일 때, 계산하기 쉽게 K = k - 1 이라고 두면 x + y = K 이므로 y = - x + K 이다. 즉 예를 들어, 위의 그림에서 직선의 방정식은 y = -x + 5 이다. y = - x + K 직선 위의 칸들 중 왼쪽 하단부터..

[백준] 2292 - 벌집 구조

문제: www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 한 칸씩 움직일 때마다 숫자가 1씩 증가한다. 한 바퀴 돌 때마다 움직여야 하는 횟수가 6씩 증가한다. 따라서 바깥으로 한 칸씩 움직일 때 지나는 수들은 계차수열이다. 이때 육각형이므로 계차는 6이다. 따라서 아래와 같은 수열을 생각해보자 2 + n(n-1)/2 * 6 = 2 + 3n(n-1) Bn = 7 + (n(n+1)/2 - 1) * 6 시계방향으로 육각형을 감싸 돌며 더 큰 육각형이 생길 때, 그 육각형의..

[백준] 2839 - 자연수를 서로 다른 두 자연수의 합으로 나타내기

문제 : www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net N = 3x + 5y 에서 x + y의 최솟값을 구하는 문제이다. ( 3

[백준] 4673 - 셀프 넘버

문제 : https://www.acmicpc.net/problem/4673 4673번: 셀프 넘버 문제 셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다. 양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 www.acmicpc.net 함수 d(n) = m 에서 n을 m의 생성자라고 한다. 이때 생성자를 갖지 않는 숫자를 셀프넘버라고 정의하고 있다. 즉 셀프넘버는..

[백준] 10818 - 배열에서 최대 최소 구하기

문제 : https://www.acmicpc.net/problem/10818 10818번: 최소, 최대 첫째 줄에 정수의 개수 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 N개의 정수를 공백으로 구분해서 주어진다. 모든 정수는 -1,000,000보다 크거나 같고, 1,000,000보다 작거나 같은 정수이다. www.acmicpc.net 수열의 최대값과 최솟값을 구하는 문제이다. 수열은 배열로 받자. 이제 입력받은 수열에서 최댓값과 최솟값을 구해야 한다. 당장 생각나는 알고리즘은 다음과 같다. 1. 변수를 하나 만들고 거기에 수열의 첫째 항을 집어넣는다. 2. 수열의 다른 모든 수들과 비교하면서, 원래 값이 더 크면 그대로 가고, 다른 수가 더 크면 변수에 그 수를 대신 집어넣는다. 최..