코딩하기 좋은날

https://www.acmicpc.net/problem/1920 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 배열을 입력받고 그 배열에 숫자가 존재하는지 찾아서 1 / 0 을 출력하는 문제입니다. 배열의 크기와 찾을 수 의 크기가 100000까지 가능하므로 하나씩 배열을 탐색하며 찾는 방법은 시간초과가 날 것입니다. 따라서 이분탐색을 이용하는 문제입니다. 이분탐색을 하기 위해서 입력받은 배열을 정렬하고 중간값을 기준으로 찾는 값과 비교하여 오른쪽 왼쪽으로 이동한 뒤 다시 중간값을 기준으로 찾으며 logN의 시간으로 탐색을 할 수 있는 방법입니다. 다음은 코드입니다. #include #include using namespace std; int N,M; int bsearch(int x, ..

https://www.acmicpc.net/problem/1654 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 k개의 랜선을 보유하고 있을 때 랜선을 잘라 N개의 개수의 랜선을 만들 때 모두 동일한 길이로 만드는데 가장 길게 할 수 있는 길이를 구하는 문제입니다. 주어진 k개 10000까지 가능하고 N이 10000000 까지 가능하므로 어떤값으로 모든 k를 나눠서 그합을 더했을 때 N이 되는지 일일이 확인한다면 시간이 많이 걸리게 될것입니다. 따라서 이분탐색을 이용하여 가장큰 값을 찾아내면 됩니다. 주의할 점은 랜선의 길이가 2^31-1까지 가능한데 중간에 두 랜선 사이의 연산이 있을 수 있어서 오버플로우 가능성이 있는 변수들은 long long으로 선언을 해주어야 합니다. 다음은 코드..

https://www.acmicpc.net/problem/2579 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 계단을 오르는데 1칸 또는 2칸을 이동 할 수 있습니다. 그런데 3칸의 계단을 연속해서 오를 수 없을때 마지막 계단에 도달하는 최대값을 구하는 문제입니다. 각계단마다 점수가 있기 때문에 dp를 이용하여 이전 계단들 까지의 값을 이용하여 마지막 계단의 값을 구하여야 합니다. 따라서 저는 2차원 배열을 선언해 0번은 바로이전 계단에서 올라온 상태이고 1번은 2칸 아래의 계단에서 올라온 상태로 정하고 계산을 하였습니다. dp[1][i] 같은경우는 i-2번째 계단에서 2칸을 이동했을 때 값이므로 이때는 dp[0][i-2] 와 dp[1][i-2] 중 더큰 값에다 계단의 값을 더해주어서 ..

https://www.acmicpc.net/problem/1149 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 N개의 집을 칠 할 때 각각의 줄에 R G B의 색으로 칠하는 비용을 입력 받습니다. 이때 서로 이웃한 i-1과 i+1번째 집은 같은색을 칠할 수 없다는 제약이 있습니다. 따라서 각각의 색깔로 칠했 을때를 dp를 이용하여 모두 저장후 최종적으로 값들을 비교해서 가장 작은 값을 출력해야 합니다. 예를들어 i번째 집을 빨간색으로 색칠 한다면 i-1번째 집을 파란색으로 색칠하는 비용과 초록색으로 색칠하는 비용중 더 적은 비용을 선택하면 됩니다. dp[0][i] = min( dp[1][i-1] + red[i], dp[2][i-1] + red[i]); 따라서 각 색깔마다 이러한 점화식이..

https://www.acmicpc.net/problem/1932 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 각각 n번째 줄에 n개의 숫자가 주어지며 삼각형을 이루는데 이때 한 원소에서 다음원소로는 왼쪽 대각선이나 오른쪽 대각선으로 이동이 가능하다면 이러한 이동경로의 최대값을 구하는 문제입니다. dp를 이용하여 각각 이전 번째 줄에서의 최대값들을 갱신후 아래쪽으로 내려가야 합니다. 그렇다면 왼쪽 대각선과 오른쪽 대각선을 어떻게 나타낼지만 해결하면 되는 문제입니다. 예를들어 숫자를 적어보면 1 2 3 4 5 6 이 있습니다. 이때 1은 [1][1]의 원소이고 2는 [2][1] 3은 [2][2] 4는 [3][1] 5는 [3][2] 6은 [3][3] 이라는것을 확인 할 수 있습니다. 따라서..

https://www.acmicpc.net/problem/6591 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 nCk를 구하는 문제입니다. 이때 n과 k가 각각 2^31-1 까지 가능하다고 되어 있습니다. 그리고 nCk의 결과값은 항상 2^31보다 작다고 되어 있으므로 아주큰 n과 k를 입력받아도 21억을 못넘으므로 그렇게 연산 횟수가 많지 않을 것이므로 nCk = nPk / k! 을 이용해서 그냥 구해주면 됩니다. 이때 주의할 점은 nCk = nCn-k 이므로 만일 1000C998 이 입력된다면 998번 연산을 하는 것이 아니라 1000C2로 바꾸어 생각하여 2번만 연산을 하게 해주어야 시간초과를 피할 수 있습니다. 그리고 답은 int형 범위 안이지만 계산하는 과정에서 그값이 초과 될..

https://www.acmicpc.net/problem/1676 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n팩토리얼을 하였을 때 끝자리부터 0이 아닌수가 나올때 까지의 0의 개수를 구하는 문제입니다. n이 500까지 가능하므로 팩토리얼을 구하는 것은 어마어마하게 큰수가 나오게 됩니다. 따라서 어떻게 하면 0을 찾을 수 있을까를 생각해보면 기본적으로 끝자리에 0이 생기기 위해서는 2와 5라는 숫자가 필요하게 됩니다. 따라서 이 숫자들의 개수를 세어주면 되는데 기본적으로 n!의 진행에서는 5보다 2가 훨씬 많으므로 저희는 5의 개수만 셈으로써 0이 몇개나오는지 알 수 있습니다. 이 때 주의할 점은 5의 제곱수가 나올 때 입니다. 25는 5가 2번 곱해진 것이므로 0을 두개 만들 수 있..

https://www.acmicpc.net/problem/1003 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n번째 피보나치 함수를 구할 때 1번째 피보나치 수와 0번째 피보나치 수가 각각 몇번 나왔는지를 구하는 문제입니다. 기본적으로 피보나치 함수를 구할 때 f(n) = f(n-1)+f(n-2) 인 성질을 이용하여 pair를 자료형으로 가지는 벡터를 하나 선언해 first 에는 0의 개수 second에는 1의 개수를 넣어주면서 구해주면 됩니다. v[i].first = v[i-1].first + v[i-2].first, v[i].second = v[i-1].second + v[i-2].second 대략 이런식으로 저장이 되어 n번째 까지 진행을 하면 답을 구할 수 있습니다. 다음은 코..