코딩하기 좋은날

https://www.acmicpc.net/problem/9461 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 삼각형이 나선형으로 놓여집니다. 이때 나선에서 가장 긴변의 길이를 k라고 하고 k길이의 정삼각형을 추가하는 방식으로 배치가 되는데 N번째 진행시 k의 값을 구하는 문제입니다. 수열을 쭉 보시면 1 1 1 2 2 3 4 5 7 9 12 ... 으로 진행되는데 n번째 값은 n-1과 n-5를 더하면 나온다는 것을 알 수 있습니다. 따라서 그에따라 점화식을 세워주면 풀리는 문제입니다. 주의할점은 n이 100까지 가능하므로 오버플로우가 일어날 수 있어 longlong형으로 선언 해주셔야 합니다. 다음은 코드입니다. #include using namespace std; int main(v..

https://www.acmicpc.net/problem/9252 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 LCS 최장공통부분수열의 길이와 그 수열을 출력하는 문제입니다. 두 문자열이 있을때 공통으로 존재하는 가장긴 수열을 구하는 것입니다. 따라서 dp를 이용하여 이전까지의 길이를 바탕으로 비교해나가는 방식을 이용하여야 합니다. 두 문자열이 있을때 각 문자열의 길이를 1씩 늘려가며 현재 비교하는 위치의 두문자열의 문자가 동일한 경우 dp의 길이를 증가시켜주는 방식을 이용하여야 합니다. 두문자열을 잡고 직접 표를 그려보시면 이해가 쉬울 것입니다. 결론적으로 if(str1[i-1] == str2[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = ..

https://www.acmicpc.net/problem/2156 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 포도주가 일렬로 놓여있을 때 가장 많은 포도주를 마실 수 있는 양을 구하는 문제입니다. 이때 연속으로 세잔의 포도주를 마실 수 없다는 조건이 있습니다. 따라서 i번째의 잔까지 왔을 때 가장 많은 포도주의 양을 구하기 위해서는 총 세가지 경우중 최대값을 찾아야 합니다. 1. i번째 포도주를 먹지 않는경우 -> dp[i-1] 2. i-1번째 포도주를 먹지 않고 i번째 포도주를 먹는 경우 -> dp[i-2] + grape[i] 3. i-1번째 포도주와 i번째 포도주를 먹는 경우 -> dp[i-3] + grape[i-1] + grape[i] 세가지의 식이 존재하고 이 세가지 중 가장 ..

https://www.acmicpc.net/problem/10844 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 n자리 숫자에서 각 인접 숫자끼리의 차이가 1 나는 숫자의 개수를 구하는 문제입니다. 저는 dp를 2차원 배열로 선언하고 하나의 인덱스는 자리수 그리고 나머지 하나의 인덱스는 끝자리 숫자를 나타내는 숫자를 뜻합니다. 이때 숫자는 0으로 시작 할 수 없고 끝자리 숫자가 0 , 9 일때는 다음에 붙는 숫자가 1과 8 만 가능합니다. 나머지 경우에는 끝자리 숫자 -1, +1 이 가능합니다. dp[i][j] = (dp[i-1][j-1] + dp[i+1][j-1]) % 1000000000 따라서 끝자리 숫자가 0,9 가 아닐때는 이러한 점화식이 나오게 됩니다. j자리 숫자중 끝자리가 ..

https://www.acmicpc.net/problem/1463 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 N이 주어졌을 때 3가지 연산을 최소로 사용하여 1을 만드는 횟수를 찾는 문제입니다. X가 3으로 나누어 떨어지면, 3으로 나눈다. X가 2로 나누어 떨어지면, 2로 나눈다. 1을 뺀다. 저는 이문제를 바텀 업 방식으로 해결하였습니다. 우선은 N이 1일때는 0입니다. N이 2일때부터 반복문을 돌리는데 N이 만약 2로 나누어 떨어진다면 이때 횟수는 dp[N-1] + 1 과 dp[N/2] + 1 중 더 작은값이 될 것입니다. N이 3일때는 마찬가지로 dp[N-1] + 1 과 dp[N/3] + 1 중 더 작은값이 될 것입니다. 저는 처음에 if(i % 2 == 0) else if(i..

https://www.acmicpc.net/problem/1005 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 w 건물을 짓는데 걸리는 최소 시간을 출력하는 문제입니다. 하나의 건물을 짓기위해서는 앞의 선행 건물들이 모두 지어져야 지을 수 있으므로 위상 정렬을 이용해야 합니다. 뭔가 계속 하나씩 코드를 잘못 적어서 무수하게 틀린 문제입니다 ㅠㅠ.. 우선은 벡터에 인접리스트 형식으로 각 정점과 연결되어 있는 정점들을 집어넣고 집어넣어지는 정점의 indegree를 하나씩 늘려줍니다. 위상정렬에서는 indegree가 0이 되는 곳이 선행자가 없는 가장 앞부분에 있는 정점입니다. 인접리스트와 indegree를 모두 완성 시킨뒤 indegree가 0인 점들부터 시작해서 다음 경로로 가장 길이가 ..

https://www.acmicpc.net/problem/1300 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 이 문제는 N*N배열이 있을 때 이 배열엔 i*j의 숫자가 들어있다고 하고 이 배열을 일차원 배열에 오름 차순으로 정렬 할때 K번째 수를 구하는 문제입니다. 처음에 분류가 이분탐색으로 되어 있어서 그렇게 생각하고 봤는데도 접근을 잘 못하겠어서 다른 글들을 참고하였습니다. 우선 배열에 i*j의 숫자들이 저장 되어 있으므로 K보다 작은 숫자의 개수를 찾고 싶다면 K/i를 해야 구할 수 있다는 것이 포인트입니다. 문제의 예시를 보면 N이 3이고 K가 7일때를 예로 들고 있습니다. 이경우 3*3 배열이므로 아래와 같이 수가 있고 예를 들어 7보다 작은 숫자의 개수를 찾고 싶다면 7/1 + 7/2..

https://www.acmicpc.net/problem/10815 문제와 채점은 위 사이트에서 확인 하실 수 있습니다 숫자카드를 배열에 입력받고 각카드가 들어 있는지 확인 한뒤 1 / 0을 출력하는 문제입니다. 그냥 배열의 앞부터 끝까지 출력하는 문제는 시간이 많이 소요되므로 배열을 정렬한뒤 이분탐색을 이용하는 문제입니다. 다음은 코드입니다. #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(NULL); int N,M; cin >> N; int arr[N]; for(int i = 0; i > arr[i]; sort(arr, arr+N); cin >> M..