Hello World

백준 2875 : 대회 or 인턴 문제 링크 www.acmicpc.net/problem/2875 2875번: 대회 or 인턴 첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N), www.acmicpc.net 문제 내용 백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.) 백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다. 백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 ..

백준 1874 : 스택 수열 문제 링크 www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 내용 1부터 n까지의 수를 스택에 넣었다가 뽑아 늘어놓음으로써, 하나의 수열을 만들 수 있다. 임의의 수열이 주어졌을 때 스택을 이용해 그 수열을 만들 수 있는지 없는지, 있다면 어떤 순서로 push와 pop연산을 수행해야 하는지를 알아내자. 이를 계산하는 프로그램을 작성하라. push..

백준 2749 : 피보나치 수 3 문제 링크 www.acmicpc.net/problem/2749 2749번: 피보나치 수 3 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 문제 내용 피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다. n이 주어질때, n번째 피보나치 수를 1,000,000으로 나눈 나머지를 출력한다. Idea 이 문제를 시간초과 없이 풀기 위해서는 피사노 주기를 알아야한다. 피사노 주기란 피보나치 수를 m으로 나눈 나머지가 주기를 이룬다는 것이다. 즉, 일정한 패턴이 존재한다는 뜻이다. 피사노 주기..

백준 9471 : 피사노 주기 문제 링크 www.acmicpc.net/problem/9471 9471번: 피사노 주기 첫째 줄에 테스트 케이스의 개수 P (1 ≤ P ≤ 1000)가 주어진다. 각 테스트 케이스는 N과 M으로 이루어져 있다. N은 테스트 케이스의 번호이고, M은 문제에서 설명한 m이다. (2 ≤ M ≤ 1,000,000) www.acmicpc.net 문제 내용 1960년, IBM의 직원 Donald Wall은 피보나치수열을 m으로 나눈 나머지가 주기를 이룬다는 것을 증명했다. 예를 들어, 피보나치 수열의 처음 10개를 11로 나눈 예는 다음과 같다. 나머지를 이용해서 만든 수열은 주기가 나타날 수 있다. k(m)을 반복하는 부분 수열의 길이라고 했을 때, k(11) = 10 임을 알 수 ..

백준 11047 : 동전 0 문제 링크 www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 문제 내용 준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다. 동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오. (단, 동전은 1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 ..

백준 16926 : 배열 돌리기 1 문제 링크 www.acmicpc.net/problem/16926 16926번: 배열 돌리기 1 크기가 N×M인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. A[1][1] ← A[1][2] ← A[1][3] ← A[1][4] ← A[1][5] ↓ ↑ A[2][1] A[2][2] ← A[2][3] ← A[2][4] A[2][5] �� www.acmicpc.net 문제 내용 크기가 NxM인 배열이 있을 때, 배열을 돌려보려고 한다. 배열은 다음과 같이 반시계 방향으로 돌려야 한다. Idea 처음엔 나름의 규칙을 찾아 연산하려 했으나... 복잡하여 그냥 하나씩 옮겼다. 아래 코드의 규칙은 다음과 같다. 가장 바깥쪽부터 회전시킨다..

백준 5585 : 거스름돈 문제 링크 www.acmicpc.net/problem/5585 5585번: 거스름돈 타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사� www.acmicpc.net 문제 내용 잔돈으로 500엔, 100엔, 10엔, 5엔, 1엔이 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 잡화점에서 물건을 사고 1000엔을 냈을 때 받을 잔돈의 개수를 구하는 프로그램을 작성하시오. 단, 지불한 돈은 1 이상 1000 미만의 정수이다. Idea 사용 알고리즘 : Greedy Algorithm ( 탐욕 알고리즘 ) 제일 ..

백준 1316 : 그룹 단어 체커 문제 링크 www.acmicpc.net/problem/1316 1316번: 그룹 단어 체커 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때� www.acmicpc.net 문제 내용 그룹 단어란 단어에 존재하는 모든 문자에 대해서, 각 문자가 연속해서 나타나는 경우만을 말한다. 예를 들면, ccazzzbb는 c, a, z, b가 모두 연속해서 나타나고, kin도 k, i, n이 연속해서 나타나기 때문에 그룹 단어이지만, aabbccb는 b가 떨어져서 나타나기 때문에 그룹 단어가 아니다. 단어 N개를 입..

백준 2675 : 문자열 반복 문제 링크 www.acmicpc.net/problem/2675 2675번: 문자열 반복 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 새 문자열 P를 만든 후 출력하는 프로그램을 작성하시오. 즉, 첫 번째 문자를 R번 반복하고, 두 번째 문자를 R번 반복하는 식으로 P를 만들면 된다 www.acmicpc.net 문제 내용 문자열 S를 입력받은 후에, 각 문자를 R번 반복해 출력하는 프로그램을 작성하시오. 문자열의 길이는 최소 1이며, 20글자를 넘지 않는다. ex) 입력 : 3 ABC 출력 : AAABBBCCC Idea 중첩 for문을 사용하여 형식에 맞춰 출력할 수 있도록 한다. Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18..

백준 1806 : 부분합 문제 링크: www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 문제 내용: 10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오. Idea: 가장 짧은 길이를 구하기 위해 두 개의 포인터를 사용한다. left : 부분합의 가장 왼쪽 인덱스를 가리키는 용도 right : 부분합의 가장 오..