CodeDrive

문제:

정육면체 모양의 상자가 일렬로 늘어서 있다. 상자마다 크기가 주어져 있는데, 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자 안에 넣을 수 있다. 예를 들어 앞에서부터 순서대로 크기가(1,5,2,3,7)인 5개의 상자가 있다면, 크기 1인 상자를 크기 5인 상자에 넣고, 다시 이 상자를 크기 7인 상자 안에 넣을 수 있다. 하지만 이렇게 상자를 넣을 수 있는 방법을 여러 가지가 있을 수 있다. 앞의 예에서 차례대로 크기가 1, 2, 3, 7인 상자를 선택하면 총 4개의 상자가 한 개의 상자에 들어가게 된다.

상자의 크기가 주어질 때, 한 번에 넣을 수 있는 최대의 상자 개수를 출력하는 프로그램을 작성하시오.

입력:

파일의 첫 번째 줄은 상자의 개수 n(1<=n<=1000)을 나타낸다. 두 번째 줄에는 각 상자의 크기가 순서대로 주어진다. 상자의 크기는 1,000을 넘지 않는 자연수이다.

출력:

첫쨰 줄에 한 줄에 넣을 수 있는 최대의 상자 개수를 출력한다.

풀이방법:

앞에 있는 작은 상자를 뒤에 있는 큰 상자에 넣을 수 있으므로 이는 다이나믹프로그래밍을 사용한 LIS 문제와 같다.

LIS에서 lis[i]는 i번째 수열까지 한 번에 넣을 수 있는 최대의 상자 개수이며, i+1을 추가했을 때, boxes[1]~boxes[i]까지 boxes[i+1]보다 작은 값이 있는지 파악하고, 그 수에 해당하는 lis[k] 값들 중에 최댓값에 1을 더해주는 방식으로 진행한다. 그러고 전체 lis에서 최댓값을 출력해주면 된다.

문제링크:

https://www.acmicpc.net/problem/1965

문제:

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우) 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력:

첫째 줄에 두 정수 N(1<=N<=200),K(1<=K<=200)가 주어진다.

출력:

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

풀이방법:

동적계획법을 사용해서 이 문제를 풀었다. 점화식은 간단하다. K개의 합이 N이 되었을 때, 맨 마지막 수( l )를 빼면 남은 수는 K-1개로 N-l 이 남는 다는 것이다. 그래서 dp 테이블을 다음과 같이 구성할 수 있다.

dp[ i ][ j ] 는 i개의 수를 가지고 합이 j가 되는 경우를 뜻한다. 따라서 처음에는 1로 초기화되며, 한 층이 지날때마다 경우의 수가 더해져 우리가 원하는 dp[k][n]을 구할 수 있다.

문제링크:

https://www.acmicpc.net/problem/2225

문제:

재원이는 한 도시의 시장이 되었다. 이 도시에는 도시를 동쪽과 서쪽으로 나누는 큰 강이 흐르고 있다. 하지만 재원이는 다리가 없어서 시민들이 강을 건너는데 큰 불편을 겪고 있음을 알고 다리는 짓기로 결심하였다. 강 주변에서 다리를 짓기에 적합한 곳을 사이트라고 한다. 재원이는 강 주변을 면밀히 조사해 본 결과 강의 서쪽에는 N개의 사이트가 있고 동쪽에는 M개의 사이트가 있다는 것을 알았다. (N<=M)

재원이는 서쪽의 사이트와 동쪽의 사이트를 다리로 연결하려고 한다. (이때 한 사이트에는 최대 한 개의 다리만 연결될 수 있다.) 재원이는 다리를 최대한 많이 지으려고 하기 때문에 서쪽의 사이트 개수만큼 (N개) 다리를 지으려고 한다. 다리끼리는 서로 겹쳐질 수 없다고 할 때 다리를 지을 수 있는 경우의 수를 구하는 프로그램을 작성하라.

입력:

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N,M(0<N<=M<30)이 주어진다.

출력:

각 테스트 케이스에 대해 주어진 조건하에 다리를 지을 수 있는 경우의 수를 출력한다.

풀이방법:

이 문제는 다이나믹 프로그래밍을 활용해서 풀 수 있는 문제이다. 

왼쪽에 3개의 사이트가 있고, 오른쪽에 5개의 사이트가 있다고 가정하자. 그럼 왼쪽의 3개와 오른쪽의 5개를 이어야 하는 문제가 된다. 하지만 왼쪽의 제일 위 점과 오른쪽의 제일 위 점에 다리를 건설했다고 하자.

이제는 아래 남은 점들은 왼쪽의 2개의 점, 오른쪽의 4개의 점을 이어야 하는 문제가 된다. 이 단계에서 한 번 더 진행하면 이제 왼쪽에는 한 개만 남고 오른쪽에는 3개, 2개 ... 가 남게 된다. 왼쪽이 1개가 되면 오른쪽에 남은 개수가 이을 수 있는 경우의 수가 되므로 이를 활용해서 점화식을 만들 수 있게 된다.

dp[i][j] = d[i-1][k-1]+d[i-1][k-2]+ ... + d[i-1][i-1]

따라서 이를 반복문으로 구현하면 다음과 같게 된다. 

https://www.acmicpc.net/problem/1010

문제:

Day of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i]로 연주 해야 한다. 하지만 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

입력:

첫째 줄에 N, S, M이 주어진다. (1<=N<=100, 1<=M<=1000,0<=S<=M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력:

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면(중간에 볼륨을 조절을 할 수 없다면) -1을 출력한다.

풀이방법:

 2차원 배열을 사용하는 동적계획법을 사용하면 트리처럼 진행이 된다. 점차 연주가 가능한 볼륨이 많아지긴 하겠지만, 0보다 작은 값이나 초과하는 값들도 들어오기 때문에 생각만큼 많이 증가하지는 않게 된다.

 각 배열은 0으로 초기화 되어 있으며 각 곡마다 연주할 수 있는 볼륨은 1로 바뀌게 된다. 따라서 처음에는 S 자리에만 1로 초기화 되어 있으며 다음 곡의 배열은 이전 곡에서 1인 값에 V[i]를 빼거나 더한 값이 1로 초기화 될 것이다.

 이렇게 마지막 곡까지 위 행위를 반복하고 뒤에서부터 1인 값을 찾아 1이면 값을 넣고 종료시키면 그 값이 최댓값이 될 것이다. 그리고 애초에 -1을 초기값으로 잡아뒀기 때문에 1인 값을 만나지 못하면 연주 할 수 없는 것을 의미하므로 답은 그대로 -1이 될 것이다.

문제링크:

https://www.acmicpc.net/problem/1495

문제:

재현이는 다음과 같은 정수 게임을 하려고 한다. 게임은 다음과 같이 이루어져 있다.

 1. 정수 N과 크기가 K인 배열 A를 정한다.

 2. 1부터 N까지 정수를 모두 종이에 쓴다.

 3. 배열 A의 가장 첫 수를 고르고, 그 수를 배열에서 제거한다. 고른 수를 x라고 했을 때, 종이에 적혀있는 수 중에 x의 배수를 지운다.

 4. 배열이 비어있을 때 까지 3번을 반복한다.

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 K가 주어진다. (1<=N<=1,000,000,000, 1<=K<=15)

둘째 줄에 배열 A의 내용이 순서대로 주어진다. 배열에 담겨있는 수는 100보다 작거나 같은 자연수이다.

출력:

게임이 모두 완료된 이후에, 종이에 적혀있는 수의 개수를 출력한다.

풀이방법:

포함배제의 원리를 사용해서 풀어야 하는 문제이다. 포함배제의 원리는 유한 집합들의 합집합의 원소를 세는 기법 중의 하나이다. 보통 다음과 같은 식을 가진다.

따라서 count를 통해서 현재 값을 더해야 하는지 빼야 하는지를 결정해준다. 해당하는 값들은 combination으로 만든 조합의 최소공배수 값을 통해서 지워야 하는 갯수를 구할 수 있다.

이렇게 포함배제로 지워지는 수들의 갯수를 구하면 n과 더해줌으로써 남은 개수를 구한다.

https://www.acmicpc.net/problem/14848

https://ko.wikipedia.org/wiki/%ED%8F%AC%ED%95%A8%EB%B0%B0%EC%A0%9C%EC%9D%98_%EC%9B%90%EB%A6%AC

문제:

해커 김지민은 잘 알려진 어느 회사를 해킹하려고 한다. 이 회사는 N개의 컴퓨터로 이루어져 있다. 김지민은 귀찮기 때문에, 한 번의 해킹으로 여러 개의 컴퓨터를 해킹 할 수 있는 컴퓨터를 해킹하려고 한다.

이 회사의 컴퓨터는 신뢰하는 관계와, 신뢰하지 않는 관계로 이루어져 있는데, A가 B를 신뢰하는 경우에는 B를 해킹하면, A도 해킹할 수 있다는 소리다.

이 회사의 컴퓨터의 신뢰하는 관계가 주어졌을 때, 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 출력하는 프로그램을 작성하시오.

입력:

첫째 줄에, N과 M이 들어온다. N은 10,000보다 작거나 같은 자연수, M은 100,000보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에 신뢰하는 관계까 A B와 같은 형식으로 들어오며, "A가 B를 신뢰한다."를 의미한다. 컴퓨터는 1번부터 N번까지 번호가 하나씩 매겨져 있다.

출력:

첫째 줄에, 김지민이 한 번에 가장 많은 컴퓨터를 해킹할 수 있는 컴퓨터의 번호를 오름차순으로 출력한다.

풀이방법:

bfs를 사용해서 이 문제를 풀었다. 이 문제에서는 신뢰 관계가 양방향으로 존재한다는 가정이 없기 때문에 신뢰 관계를 정리 할 때, 단방향으로만 해야 한다. 일반적인 리스트를 사용해도 상관이 없지만 python의 시간 초과를 해결하기 위해 deque를 사용하고자 하였다. 하지만 그래도 python으로는 시간초과가 발생하였고,(한 명도 python으로 통과한 사람이 아직 없다.)그래서 결국 pypy3으로 통과했다.

 그 외의 특이사항으로는 방문했는지 확인하는 배열인 conti가 존재한다는 것이다. 아직 방문하지 않는 컴퓨터일 때에만 값을 갱신하며 count가 증가하도록 했다.

문제링크:

https://www.acmicpc.net/problem/1325

문제:

2019/10/29 - [Algorithm/Python] - [BOJ]7576. 토마토

 위 문제에서 더 발전한 문제로 이제 한 층이 아닌 여러 층에 대해서 토마토가 익는 것이 전이된다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M,N과 쌓아올려지는 상자의 수를 나타내는 H가 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단, 2<=M<=100,2<=N<=100,1<=H<=100이다. 둘째 줄부터는 가장 밑의 상자부터 가장 위의 상자까지에 저장된 토마토들의 정보가 주어진다. 즉, 둘째줄부터 N개의 줄에는 하나의 상자에 담긴 토마토의 정보가 주어진다. 각 줄에는 상자 가로줄에 들어있는 토마토들의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 익지 않은 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다. 이러한 N개의 줄이 H번 반복하여 주어진다.

출력: 

여러분은 토마토가 모두 익을 때까지 최소 며칠이 걸리는지를 계산하여 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지는 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

 이전문제에선 2차원 배열로 받았지만, 이번에는 3차원 배열로 작성한다. 또한 위, 아래로도 이동해야 하기 때문에 dx,dy,dn 세 가지 변수를 사용했다. 이외에는 이전문제와 동일한 풀이로 풀었다.

문제링크:

https://www.acmicpc.net/problem/7569

문제:

철수의 토마토 농장에서는 토마토를 보관하는 큰 창고를 가지고 있다. 토마토는 아래의 그림과 같이 격자 모양 상자의 칸에 하나씩 넣어서 창고에 보관한다.

창고에 보관되는 토마토들 중에는 잘 익은 것도 있지만, 아직 익지 않은 토마토들도 있을 수 있다. 보관 후 하루가 지나면, 익은 토마토들의 인접한 곳에 있지 않은 토마토들은 익은 토마토의 영향을 받아 익게 된다. 하나의 토마토의 인접한 곳은 왼쪽, 오른쪽, 앞, 뒤 네 방향에 있는 토마토를 의미한다. 대각선 방향에 있는 토마토들에게는 영향을 주지 못하며, 토마토가 혼자 저절로 익는 경우는 없다고 가정한다. 철수는 창고에 보관된 토마토들이 며칠이 지나면 다 익에 되는지, 그 최소 일수를 알고 싶어 한다.

토마토를 창고에 보관하는 격자모양의 상자들의 크기와 익은 토마토들과 익지 않은 토마토들의 정보가 주어졌을 때, 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라. 단, 상자의 일부 탄에는 토마토가 들어있지 않을 수도 있다.

입력:

첫 줄에는 상자의 크기를 나타내는 두 정수 M, N이 주어진다. M은 상자의 가로 칸의 수, N은 상자의 세로 칸의 수를 나타낸다. 단 2<=M,N<=1,000 이다. 둘째 줄부터는 하나의 상자에 저장된 토마토들의 정보가 주어진다. 즉, 둘째 줄부터 N개의 줄에는 상자에 담긴 토마토의 정보가 주어진다. 하나의 줄에는 상자 가로줄에 들어있는 토마토의 상태가 M개의 정수로 주어진다. 정수 1은 익은 토마토, 정수 0은 잊지 않는 토마토, 정수 -1은 토마토가 들어있지 않은 칸을 나타낸다.

출력:

여러분은 토마토가 모두 익을 때까지의 최소 날짜를 출력해야 한다. 만약, 저장될 때부터 모든 토마토가 익어있는 상태이면 0을 출력해야 하고, 토마토가 모두 익지 못하는 상황이면 -1을 출력해야 한다.

풀이방법:

BFS를 사용해서 풀어야 하는 문제이다. 우선 1이 있는 위치를 파악을 하고 이를 queue에 넣어 준다. 그 뒤에 1을 하나씩 빼면서 옆에 있는 토마토를 익게 만들 수 있는지 계산을 한다. 이 때 change라는 bool 변수를 만들어서 하나의 토마토라도 queue 진행 중에 익게 된다면 True로 바뀌어서 다음 진행을 계속해서 하도록 한다. 만약 익게 되는 토마토가 없어서 False로 남아 있다면 다 익어서 종료가 된 것인지, 혹은 모두 익지 못하는 상황인지 전체를 한 번 탐색하여 파악한다.

처음부터 모두가 익어 있으면 0을 출력해야 하지만 첫 count는 항상 1부터 시작하기 때문에 count-1을 한 값을 출력하면 답을 얻을 수 있다.

문제링크:

https://www.acmicpc.net/problem/7576

문제:

Day of Mourning의 기타리스트 강토가 사용하는 기타에서 N개의 줄이 끊어졌다. 따라서 새로운 줄을 사거나 교체해야 한다. 강토는 되도록이면 돈을 적게 쓰려고 한다. 6줄 패키지를 살 수도 있고, 1개 또는 그 이상의 줄을 낱개로 살 수도 있다.

끊어진 기타줄의 개수 N과 기타줄 브랜드 M개가 주어지고, 각각의 브랜드에서 파는 기타줄 6개가 들어있는 패키지의 가격, 낱개로 살 때의  가격이 주어질 때, 적어도 N개를 사기 위해 필요한 돈의 수를 최소로 하는 프로그램을 작성하시오.

입력:

첫째 줄에 N과 M이 주어진다. N은 100보다 작거나 같은 자연수이고, M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 M개의 줄에는 각 브랜드의 패키지 가격과 낱개의 가격이 공백으로 구분하여 주어진다. 가격은 0보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력:

첫째 줄에 기타줄을 적어도 N개 사기 위해 필요한 돈의 최솟값을 출력한다.

풀이방법:

여러 개의 기타줄에서 패키지 가격이 가장 작은 값과, 낱개 가격이 가장 작은 값만 필요하다. 이 두 개의 가격을 비교했을 때, 만약 낱개로 6개를 사는 것이 패키지 가격보다 싸다면 모든 기타줄을 낱개로 사는 것이 이득이다.

만약 그렇지 않다면 사야하는 기타줄을 6으로 나눴을 때 그 몫만큼은 패키지로 사는 것이 이득이다. 그 뒤로는 남은 나머지를 낱개로 샀을 때와 패키지로 샀을 때(적어도 N개를 구매하면 되므로 초과해서 사도 괜찮다.) 어떤 것이 이득인지 알아보고 그에 맞게 구매를 해야 한다. (ex 패키지 7 낱개 2면 패키지가 더 이득)  

문제링크:

https://www.acmicpc.net/problem/1049

문제:

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력:

첫째 줄에 상근이의 동기의 수 n(2<=n<=500)이 주어진다. 둘째 줄에는 리스트의 길이 m(1<=m<=10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai,bi가 주어진다. (1<=ai<bi<=n) ai와 bi가 친구라는 뜻이며, bi 와 ai도 친구관계이다.

출력:

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

풀이방법:

우선 입력으로 받은 값들을 그래프 형식으로 정리를 하는 작업을 거친다. 이후 BFS 방식을 사용해서 level이 2까지 가는 친구들(친구의 친구)을 찾는다. 항상 시작은 1이므로 queue에 1을 넣고 BFS 탐색을 두번 한다. 그렇게 탐색을 마치고 1을 제거한 뒤에 배열의 길이를 출력하도록 한다.

문제링크:

https://www.acmicpc.net/problem/5567