YANGORITHM

문제 https://www.acmicpc.net/problem/2644 2644번: 촌수계산 사람들은 1, 2, 3, …, n (1≤n≤100)의 연속된 번호로 각각 표시된다. 입력 파일의 첫째 줄에는 전체 사람의 수 n이 주어지고, 둘째 줄에는 촌수를 계산해야 하는 서로 다른 두 사람의 번호가 주어진다. 그리고 셋째 줄에는 부모 자식들 간의 관계의 개수 m이 주어진다. 넷째 줄부터는 부모 자식간의 관계를 나타내는 두 번호 x,y가 각 줄에 나온다. 이때 앞에 나오는 번호 x는 뒤에 나오는 정수 y의 부모 번호를 나타낸다. 각 사람의 부모는 최대 www.acmicpc.net 풀이 A와 B 사이에 거리를 구하는 문제이다. 그래프 탐색인 bfs를 이용해서 A에서 B까지 거리를 구하면 된다. 만약 가는 경로가..

문제 https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되 www.acmicpc.net 풀이 N번째 자리에 올 수 있는 수는 0 또는 1이다. ○ ○ ○ .... ☆ ● 에서 만약 ●에 0이 온다면 ☆에는 0 또는 1이 ..

문제 https://www.acmicpc.net/problem/1743 1743번: 음식물 피하기 문제 코레스코 콘도미니엄 8층은 학생들이 3끼의 식사를 해결하는 공간이다. 그러나 몇몇 비양심적인 학생들의 만행으로 음식물이 통로 중간 중간에 떨어져 있다. 이러한 음식물들은 근처에 있는 것끼리 뭉치게 돼서 큰 음식물 쓰레기가 된다. 이 문제를 출제한 선생님은 개인적으로 이러한 음식물을 실내화에 묻히는 것을 정말 진정으로 싫어한다. 참고로 우리가 구해야 할 답은 이 문제를 낸 조교를 맞추는 것이 아니다. 통로에 떨어진 음식물을 피해가기란 쉬운 일이 아 www.acmicpc.net 풀이 상하좌우로 탐색하며 음식물이 있는지 없는지 검사하여 최대값을 찾으면 된다. 1. 2차원 배열을 돌면서 음식물이 있는 곳(1)..

문제 https://www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 효과적인 배추흰지렁이를 구입하기로 결심한다. 이 지렁이는 배추근처에 서식하며 해충을 잡아 먹음으로써 배추를 보호한다. 특히, 어떤 배추에 배추흰지렁이가 한 마리라도 살고 있으면 이 지렁이는 인접한 다른 배추로 이동할 수 있어, 그 배추들 역시 해충으로부터 보호받을 수 있다. ( www.acmicpc.net 끊어지지 않고 이어져있는 그래프의 수가 몇개 인지 찾는 문제이다. 즉 컴포넌트의 개수를 찾으면 된다. 풀이 입력받은 배추의 위치..

문제 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 A를 B번 곱한후 C로 나누는 시도를 하면 시간도 초과할 수 있고, 연산 값도 엄청나게 커져서 결과가 제대로 안나온다. B가 엄청나게 커지면 곱셈하는데 시간을 다 소모하게 된다. 다음과 같은 나머지 연산에 대한 공식이 있다. A * B % C = (A % C) * (B % C) % C 그리고 곱셈 연산의 수를 줄이기 위해 다음과 같은 규칙을 이용한다. 10 ^ 10 = (10 ^ 5)의 제곱 , 지수가 짝수일 경우 10 ^ 11 = (10 ^ 5)의 ..

문제 https://www.acmicpc.net/problem/9465 9465번: 스티커 문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점 www.acmicpc.net 풀이 첫 번째 열에서 스티커를 떼지 않으면 두 번째 열에서 가능한 선택은 세가지다. 위 스티커를 떼거나 아래 스티커를 떼거나 스티커를..

문제 https://www.acmicpc.net/problem/10448 10448번: 유레카 이론 문제 삼각수 Tn(n ≥ 1)는 [그림]에서와 같이 기하학적으로 일정한 모양의 규칙을 갖는 점들의 모음으로 표현될 수 있다. [그림] 자연수 n에 대해 n ≥ 1의 삼각수Tn는 명백한 공식이 있다. Tn = 1 + 2 + 3 + ... + n = n(n+1)/2 1796년, 가우스는 모든 자연수가 최대 3개의 삼각수의 합으로 표현될 수 있다고 증명하였다. 예를 들어, 4 = T1 + T2 5 = T1 + T1 + T2 6 = T2 + T2 or 6 = T www.acmicpc.net 풀이 K보다 작은 삼각수를 구해서 모두 구해서 합으로 표현가능한지 확인한다. 1000보다 작은 삼각수의 수는 생각보다 많지 ..

문제 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 이 문제의 경우 N을 1로 만드는 최소 횟수를 f(N) 이라 하면 점화식은 다음과 같이 나온다. f(N) = min { 0 (N=1일 때) f(N/3) + 1 (N이 3의 배수일 때) f(N/2) + 1 (N이 2의 배수일 때) f(N-1) + 1 } N/3, N/2, N-1을 했을 경우 연산의 횟수를 추가해야 하므로 + 1을 해준다. 코드 탑다운 방식 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31..

문제https://www.acmicpc.net/problem/3085 3085번: 사탕 게임문제 상근이는 어렸을 적에 "봄보니 (Bomboni)" 게임을 즐겨했다. 가장 처음에 N×N크기에 사탕을 채워 놓는다. 사탕의 색은 모두 같지 않을 수도 있다. 상근이는 사탕의 색이 다른 인접한 두 칸을 고른다. 그 다음 고른 칸에 들어있는 사탕을 서로 교환한다. 이제, 모두 같은 색으로 이루어져 있는 가장 긴 연속 부분(행 또는 열)을 고른 다음 그 사탕을 모두 먹는다. 사탕이 채워진 상태가 주어졌을 때, 상근이가 먹을 수 있는 사탕의 최대 개수를 구하www.acmicpc.net  풀이양옆으로 바꾸고 보드 전체를 검사하고 위아래로 바꾸고 보드 전체를 검사해야 한다.보드 전체를 검사할 때도 가로 줄 검사와 세로줄 ..

문제https://www.acmicpc.net/problem/1912 1912번: 연속합첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.www.acmicpc.net 풀이연속된 수열 중 최대 값을 찾아야 하는 문제이다. 수열을 처음부터 차례로 더하면서 더한 결과가 0보다 크면 우선순위 큐에 저장을 한다. 만약 더한 결과가 0보다 작으면 그 수열 조합은 최대값이 될 수 없으므로, 그 다음 값 부터 수열을 시작해서 다시 최대값을 찾는다. 만약 우선순위 큐가 비었다면 배열에는 0보다 큰 값이 없는 것이다. 따라서 배열을 내림차순으로 정렬하면 된다.  코드c++123456789..