문제In Programming Land, there are several pathways called Philosopher’s Walks for philosophers to have a rest. A Philosopher’s Walk is a pathway in a square-shaped region with plenty of woods. The woods are helpful for philosophers to think, but they planted so densely like a maze that they lost their ways in the maze of woods of a Philosopher’s Walk.Fortunately, the structures of all Philosopher..
문제한수는 2차원 배열 (항상 2^N * 2^N 크기이다)을 Z모양으로 탐색하려고 한다. 예를 들어, 2*2배열을 왼쪽 위칸, 오른쪽 위칸, 왼쪽 아래칸, 오른쪽 아래칸 순서대로 방문하면 Z모양이다.만약, 2차원 배열의 크기가 2^N * 2^N라서 왼쪽 위에 있는 칸이 하나가 아니라면, 배열을 4등분 한 후에 (크기가 같은 2^(N-1)로) 재귀적으로 순서대로 방문한다.다음 예는 2^2 * 2^2 크기의 배열을 방문한 순서이다.N이 주어졌을 때, (r, c)를 몇 번째로 방문하는지 출력하는 프로그램을 작성하시오.다음 그림은 N=3일 때의 예이다.입력첫째 줄에 N r c가 주어진다. N은 15보다 작거나 같은 자연수이고, r과 c는 0보다 크거나 같고, 2^N-1보다 작거나 같은 정수이다출력첫째 줄에 문제..
문제김지민은 세계적인 기타 플레이어이다. 불행하게도 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 세계적인 기타리스트인 김지민은 되도록이면 돈을 적게 쓰려고 한다. 김지민은 6줄 패키지를 살 수도 있지만, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의 가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.입력첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주..
문제세준이는 양수와 +, -, 그리고 괄호를 가지고 길이가 최대 50인 식을 만들었다. 그리고 나서 세준이는 괄호를 모두 지웠다.그리고 나서 세준이는 괄호를 적절히 쳐서 이 식의 값을 최소로 만들려고 한다.괄호를 적절히 쳐서 이 식의 값을 최소로 만드는 프로그램을 작성하시오.입력첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 많이 연속되는 숫자는 없다. 수는 0으로 시작할 수 있다.출력첫째 줄에 정답을 출력한다. 탐욕법으로 풀 수 있는 대표적인 문제이다. 이 문제를 푸는 방법은, -가 등장할 때마다 괄호를 쳐주면 된다는 것이다. 예제로 55-50+40-32+..
문제한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.입력첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 ..
ATM 문제는 순서를 바꿔도 상관 없는 문제입니다. 직관적으로 탐욕법으로 풀 수 있다는 걸 눈치챌 수 있습니다. 하지만, 최적 부분구조가 성립하는지 증명을 해보도록 하겠습니다. N명의 사람들이 서 있다고 할 때, 우리가 정답으로 고른 순서가 S1, S2, S3, S4, S5라고 해봅시다. 그리고, S1>S2라고 가정해보겠습니다. 이때 걸리는 총 시간은 S1, S1+S2, S1+S2+S3, S1+S2+S3+S4, S1+S2+S3+S4+S5의 합입니다. 즉, 5*S1 + 4*S2 + 3*S3 + 2*S4 + 1*S5이 됩니다. 하지만, S1 > S2이므로, S1과 S2의 위치를 바꿔서 5*S2 + 4*S1 + 3*S3 + 2*S4 + 1*S5로 계산하면 우리가 원래 정답으로 고른 순서보다 작은 답을 얻을 수..
백준 온라인 저지에서 본 지는 오래되었지만, 최근에 푼 BFS문제입니다. N by M이 먼저 주어지며(입력은 M,N순서로 들어왔습니다) 익은 토마토가 있는 곳의 값은 1, 빈 곳의 값은 -1, 익지 않은 토마토가 있는 곳의 값은 0으로 입력이 주어집니다. 이 때, 주어진 예제를 보면 맨 처음 익은 토마토의 개수가 1개인 경우만 볼 수 있습니다. 하지만, 처음 입력으로 들어오는 익은 토마토의 개수가 1개가 아닐 수 있음에 주의해야 합니다. 이런 류의 문제는, 대부분 BFS로 해결할 수 있습니다. BFS는 전체 경우의 수를 탐색하는데도 쓰이지만, 각 시간별 상태를 탐색할 때 간단하게 사용할 수 있는 방법인 것 같습니다. 예제를 볼까요? 예제 입력 1 복사6 4 0 0 0 0 0 0 0 0 0 0 0 0 0 ..
이 문제는 여러가지 방법을 사용해야 풀 수 있는 문제였습니다. 첫 번째로, Fastpower알고리즘입니다. (자세한 내용은 링크 참고)두 번째로, 정수론 중, 정수 연산에 대한 모듈러 연산 적용 방법입니다. 위에 링크해 둔 곳에선, 두 가지 내용 모두를 다루고 있으니 참고하시기 바랍니다. 아래는 그 구현체입니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#define _CRT_SECURE_NO_WARNINGS#include using namespace std; typedef long long LL; //10의 9승 + 7로 나눈 나머지를 ..
문제 풀이에 사용된 것은 Greedy Method로, 매 순간마다 최적의 해를 추구하는 방법이라 저렇게 이름이 붙었습니다. 편의점이나 카페에서, 잔돈을 거슬러 주는 방법과 유사합니다. 되게 직관적이죠. 예를 들어, 490원을 10원, 50원, 100원, 500원으로 남겨주는 방법의 개수를 찾는다면? 다음과 같은 방법이 있을 수 있습니다. a. 10원짜리 49개. b. 100원짜리 4개, 10원짜리 9개 c. 100원짜리 4개, 50원짜리 1개, 10원짜리 4개 등등... 이미 깨달으신 분도 계시겠지만, 큰 돈부터 먼저 채워나가면 동전의 개수를 최소화할 수 있습니다. 아래는 그 소스코드 입니다.12345678910111213141516171819202122232425262728293031#include #..
유명하고, 간단한 DP문제입니다. 가치가 X원이 되는 모든 경우의 수를 A(x)라고 했을 때, 입력받은 동전이 1, 2, 5원이고 10원을 만든다고 하면 (예제 1) A(10)은 A(9)+1원, A(8)+2원, A(5)+5원이라고 할 수 있고, A(9) = A(8) + A(7) + A(4)A(8) = A(7) + A(6) + A(3)A(5) = A(4) + A(3) + A(0) cf) A(0)=1... 이런식으로 여러가지의 점화식이 생깁니다. 중복되는 항이 많으므로, Dynamic Programming 기법을 사용해 문제를 풀면 아래의 소스코드와 같이 풀 수 있습니다. 1234567891011121314151617181920212223242526#include using namespace std; typ..