백준
[C++/백준] 11399 ATM
문제 인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다. 사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다..
[C++/백준] 1931 회의실 배정
문제 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다. 입력 첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거..
[C++/백준] 백준 7576 토마토
문제 철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다. 창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있는 익지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익게 되는지, 그 최소 일수를 알고 싶어 한다. 토마토를 창고에 보관하는 격자모양의 상자들..
[C++/ 백준] 2606 바이러스
백준 2606 바이러스 문제 신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 ..
[c++/백준] 1697 숨바꼭질
백준 1697 숨바꼭질 문제 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 1초 후에 2*X의 위치로 이동하게 된다. 수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시오. 입력 첫 번째 줄에 수빈이가 있는 위치 N과 동생이 있는 위치 K가 주어진다. N과 K는 정수이다. 출력 수빈이가 동생을 찾는 가장 빠른 시간을 출력한다. BFS를 사용해서 푸는 문제이다. 수빈이가 택..
가장 긴 증가하는 부분 수열_ 백준11053
백준 11053 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오 수열의 길이와 수열의 값을 입력받아 가장 긴 증가하는 부분수열을 구하는 문제이다. 이 문제 역시 DP 문제 이므로, d[i]를 구하는 것이 중요한데, d[1] = 1 d[i]와 d[i-1] ~ d[1]의 관계 ← 이 부분에서 주의해서 살펴보았다. '가장 긴 증가하는 부분수열' 이 되기 위해서는 앞에 있는 수 중 i번째 숫자보다 작으며, d의 값이 가장 큰 것을 찾아야 한다. 그 이후에는, 그 값(d[j])에 1을 더하면, 우리가 구해야 하는 d[i]값이 나온다. 해당 내용에 맞추어 코드를 짜면 아래와 같다. #include using namespace std; int nums[1001]; int d[100..
이친수_2193
2193 N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 이친수: 이진수중 다음의 두 조건을 만족하는 수. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 그러므로 점화식을 세울 때 우리는 끝의 문자에 따라 d[n][1], d[n][0]으로 나누어 생각하여야 한다. 이친수는 0으로 시작하지 않으므로 초기값은 d[1][1] = 1, d[1][0] = 0 이다. 그렇다면 이 초기값을 기준으로, 나머지 점화식을 세울 수 있다. 여기서는 두번째 조건에 집중하면 된다. 1은 연속해서 사용할 수 없기 때문에 두번째 조건에 집중하면 점화식은 d[n][1] = d[n-1][0], d[n][0] ..
쉬운 계단 수 _ 백준 10844
10844 N이 주어질 때, 길이가 N인 계단 수가 총 몇 개 있는지 구하는 프로그램을 작성하시오. (0으로 시작하는 수는 없다.) 계단 수 : 인접한 모든 자리수의 차이가 1인 수. 여기서 d[n] = 길이가 N인 계단 수의 개수라고 볼 수 있지만, 여기서 우리는 인접한 수의 차이가 1 인것도 고려해야 한다. 그렇다면 마지막 숫자를 배열에 추가하여 d[n][i] = 길이가 n인 계단 수이며, 마지막 숫자가 i인것으로 하여 점화식을 세우면 된다. 처음에 잘못생각해서, 마지막 숫자가 아니라 첫번째 숫자로 생각했더니 문제가 발생했기 때문에... 마지막 숫자라는 것을 유의했으면 좋겠다. 따라서 점화식을 세우면 d[n][i] = d[n-1][i-1] + d[n-1][i+1]이다. 다만, i가 0, 9 일 때에는..
1, 2, 3 더하기 5_ 백준15990
15990 정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오. 단, 같은 수를 두 번 이상 연속해서 사용해서는 안됩니다. 1,2,3더하기의 심화버전인 문제이다. n이 주어졌을 때 1,2,3만의 합으로 구하는 것이며, 같은 수를 두번 이상 연속해서 사용하면 안된다는 조건이 추가되었다. 그렇다면, 같은 수인지 아닌지 확인하기 위한 추가적인 절차가 필요하다. 이를 위해서 정수의 값을 저장할 부분을 이차원 리스트로 만들었다. 즉, n이 주어졌을 1,2,3의 합으로 나타내는 경우의 수를 d[n]이라 하면 d[n] = d[1] + d[n-1] d[n] = d[2] + d[n-2] d[n] = d[3] + d[n-3] 이므로, n이 주어졌을 때 위의 세 사례로 나..
카드구매하기 _ 백준 11052& 백준 16194
이번에도 역시 DP와 관련된 문제이다. 11052 카드 N개를 구매하는 비용의 최대값을 구하는 문제. 카드 N개를 구매하는 비용의 최대값을 d[N]이라고 하면 d[N] = max(d[i] + d[N-i]) 이다. 그러므로 d[1]의 값을 넣고, 그 다음 값부터는 for문을 통해서 확인하며 수행한다. 여기서 j의 값이 i/2인 이유는 i/2이후부터는 d[j] + d[i-j]의 순서만 다를 뿐, 결과는 같기 때문에 계산을 줄이고자 값을 제한한 것이다. //11502 - 카드 구매하기 #include using namespace std; int d[1001]; int f[1000]; int main(void) { int count; int num; int i = 1; scanf("%d", &count); nu..