오답노트

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net - 문제파악 정수 N이 주어지고 수의 자리가 오름차 순인 N자리 수를 만들 수 있는 경우의 수를 출력하라 - 정답 이런 문제 이전에 계속 당해서 조금 생각하니 풀렸다. D[i][j]를 선언했다 i는 자리수 j는 마지막에 오는 수의 경우의 수이다. 예를 들어 i =2 이고 j =3 이면 3이 마지막으로 오는 오르막 수를 만드는 경우의 수는 D[2][3]이다. N ..

https://www.acmicpc.net/problem/1309 1309번: 동물원 첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다. www.acmicpc.net - 문제파악 정수 n이 주어진다. 2*N 행렬이 있을때 0마리 부터 N 마리의 사자를 인접하지 않도록 놓는 경우의 수를 출력하라 - 나의 접근 이중배열은 생각했지만 나는 n이 1일 때 0마리부터 n마리를 넣는 배열로 생각했었다 그러면 시간복잡도가 최대 n*(n-1) 이므로 n이 10만이면 바로 시간초과 여기서 또 막혔다. - 정답 사자를 몇마리를 넣을지가 아니라 이전에 넣었던 사자의 위치로 이전 값에 더하는 식으로 접근해야한다. D[i][j] 에서 i 는 세로 길이 j 는 0 일때는 사자를 두지 않는 경우 1은 오른쪽 2는 왼쪽이..

https://www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net - 문제 파악 정수 n 과 n * 3 의 배열이 주어진다. 이전에 사용했던 배열의 위치를 사용하지 않는 배열의 합 중 최소값을 구하라. - 나의 접근 2^n * 3 의 알고리즘 밖에 떠오르지 않고 아래와 같은 반례 때문에 간단한 문제임에도 쉽게 풀어내지 못했다. 내가 생각한 반례 3 1 2 100 100 100 100 1 1 1 최소값을 선택해서 나아간다는 단순한 알고리즘으로..

https://www.acmicpc.net/problem/15988 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net - 문제 파악 주어진 정수 n을 1, 2, 3의 합으로 나타낼 수 있는데 그 방법의 수를 출력하라. - 정답 난 1, 2, 3이 더해지는 경우를 생각했다. 정수 n이 되기 위해 n - 1의 모든 경우의 수에 1을 더하면 n이 되고, 정수 n이 되기 위해 n - 2의 모든 경우의 수에 2를 더하면 n이 되고, 정수 n이 되기 위해 n - 3의 모든 경우의 수에 3을 더하면 n이 된다. #include "bits/stdc++.h" using names..

https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net - 문제 파악 자연수 N이 주어지면 그 수는 어떠한 제곱수의 합들로 표현할 수 있다. 최소항으로 만들 때 그 개수를 출력하라. - 나의 접근 질문을 뒤져보니 나와 같은 방식으로 많이 접근한 것 같다. 일단 주어진 수의 sqrt 한 값을 다시 제곱했을 때 자기 자신일 경우 그 수로 대체하여 계속 1의 제곱을 더해 나가는 것. 하지만 이런식으로 하면 12에서 많..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net - 문제 파악 주어진 수열에서 1개 이상의 연속되는 수를 선택하여 선택한 수들의 합의 최댓값을 출력하라. - 나의 접근 i 번째 부터 n번째 모두 더하는데 그중에 가장 큰 값을 D 배열에 넣어놨다. 일단 위와 같은 경우는 시간 초과에 당연히 걸리며, 점화식을 전혀 활용하지 못했다. for문을 한번만 사용해야한다는 것 까지는 깨달았지만, D를 어떤 식으로 사용해야할지 더 이상 생각나지 않았다. - 정답 DP ..

https://www.acmicpc.net/problem/14002 14002번: 가장 긴 증가하는 부분 수열 4 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 문제 파악 주어지는 수열에서 적절히 수를 제거하여 증가하는 수열을 만드는데 길이가 가장 긴 수열의 길이와 그 수열을 출력하라. -정답 기본적으로 https://dhjkl123.tistory.com/58 문제와 같고 추가 적으로 가장 긴 증가하는 부분 수열을 출력하는 문제이다. D배열에 넣는 길이가 변할 때마다 영..

https://www.acmicpc.net/problem/11053 11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이 www.acmicpc.net - 문제 파악 주어진 수열에서 부분적으로 제거 하여 증가하는 수열을 만들 때 가장 긴 수열의 길이를 출력하라 - 나의 접근 1. 0부터 N까지 주어진 배열을 확인하며, arr[i] 와 가장 차이가 적게 나는 배열을 찾아 거기에 arr[i]+1 값을 넣도록 했다. -> 경우의 수를 너무 좁혀서 다 안찾아지는 그런 경우가 ..

https://www.acmicpc.net/problem/10844 10844번: 쉬운 계단 수 첫째 줄에 정답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net - 문제 파악 이웃한 자리수의 숫자의 차가 1인 수를 계단 수라고 한다. 정수 N이 주어졌을 때, N자리 계단 수를 만들 경우의 수를 구하여라. (0으로 시작하는 계단수는 없음, 0 이전의 수는 없음, 9 다음의 수는 없음) - 나의 접근 N 자리일때 2^(N-1)의 경우가 생기는데 여기서 위와 같은 경우를 빼는 식으로 접근 배열로 안풀려도 풀릴거 같아서 위와 같은 방법으로 접근 했지만 DP 는 배열을 선언해야한다. - 정답 D[i][j] 는 i 번째 자리에 j 가 오는 경우 D[i][j] 는 D[i][j-1]..

https://www.acmicpc.net/problem/15990 15990번: 1, 2, 3 더하기 5 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net - 문제 파악 정수 N과 N개의 정수가 주어진다. 각각의 정수를 1,2,3의 합으로 나타낼 수 있는 경우의 수를 출력하라. 단, 1,2,3 중 1개 이상의 숫자를 써야하고 연속해서 사용할 수 없다. - 나의 접근 시간복잡도를 신경안쓰고 일단 초항으로 1, 2, 3을 먼저 초기화하고 4부터 for문을 돌리도록 했는데 초항에 대한 문자열을 초기화하여 무식하게 앞뒤로 붙혀가면서 연속되면 경우의 수에서 제외 해버리는 알고리즘으로 접근했으나, 예상대로 시간..