IT세상

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp[n]은 n개를 구입 할 때 최대 금액으로 정하고 n=1 은 p[1]로 초기화한다 그리고 n=2부터 dp[n] = dp[n-i] + dp[i] 의 점화식을 이용해 풀면 된다 #include using namespace std; int n; int p[1001], dp[1001]; int main(void) { cin >> n ; for(int i=1; i> p[i]; } dp[1] = p[1]; fo..

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 전에 풀어봤던 문제라서 쉽게 해결됐다 배열 a에 수열을 넣고 dp배열에는 i번째 값을 포함하는 가장 긴 수열의 수를 넣는다 dp배열은 1로 초기화하고 a값을 차례대로 비교하면서 자신의 값보다 작은 값의 dp값에 1을 더해준다 #include using namespace std; int n; int dp[1001] = {..

내가 보기에 이 책의 결론은 크게 1. 지금 하고 있는 일을 사랑해라 2. 누구에게도 뒤지지 않을 만큼 노력해라 인 것 같다 책 초반에는 일에 미친 사람인가 했고 읽으면서는 왠지 사장님들이 좋아할 내용 같다는 생각을 했다 나는 일을 생계를 위해 마지못해 하는 사람은 아니고 그래도 즐겁게 하는 편이라 공감되는 내용도 있었다 현재의식과 잠재의식에 대한 이야기가 나오는데 나는 코드를 짜다가 해결을 못하고 퇴근했는데 샤워하다가 갑자기 방법이 떠오르는 경험을 한 적이 있었다 개발자 밈 같은 글도 나와서 웃겨서 찍었다 물론 책 내용에서는 우스갯소리가 아니라 뒤에 진지한 내용이 나옴 그리고 이런 내용은 직장인뿐만 아니라 시험준비를 한다거나 해서 확신이 필요한 사람들에게 용기를 줄 수 있는 내용인 것 같기도 했다 책을..

https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 스티커 점수를 담는 배열 arr[i][j] 와 (i. j)를 포함하는 스티커 점수의 최대값 dp[i][j] 배열을 선언해준다 j열의 점수를 계산하면 j-1 대각선에 있는 점수랑 j-2 대각선에 있는 점수 중 큰 값을 비교해 자신의 값과 더해주면 된다 #include using namespace std; int t, n; int dp[2][100001], arr[2][100001]; vo..

https://www.acmicpc.net/problem/9461 9461번: 파도반 수열 오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 www.acmicpc.net 처음에는 숫자 배열만 보고 p[n] = p[n-2] + p[n-3] 라고 생각했는데 직접 그림을 그려보니 p[n] = p[n-1] + p[n-5] 였다 그리고 어느순간 int의 범위를 벗어나서 배열은 long long 형으로 선언했다 #include using namespace std; int tc; long long a[101] ={0,1,1,1,2,2}; int main(void) { cin >> ..

https://www.acmicpc.net/problem/2193 2193번: 이친수 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다. 이친수는 다음의 성질을 만족한다. 이친수는 0으로 시작하지 않 www.acmicpc.net 두가지 방법으로 풀 수 있는 것 같다 다른 블로그들을 찾아보니 피보나치 수열로 많이 푼 것 같다 나는 다른 규칙을 찾아서 dp[n][s] : s로 끝나는 n자리 이친수 개수라고 정하고 dp[n][0] = dp[n-1][0] + dp[n-1][1] dp[n][1] = dp[n-1][0] 라는 점화식을 가지고 코드를 짰다 #include using namespace std; int n; l..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 원래는 dp[n]으로만 식을 세웠었는데 예시를 적다보니 일의자리 수가 중요하다고 생각되어 일의자리 s를 추가했다 길이가 n이고 일의자리 수가 s인 오르막수의 개수는 길이가 n-1이고 일의자리수가 0부터 s까지인 오르막수의 개수를 모두 더하면 된다 저 sum함수를 너무오랜만에 써봐서 맞게 썼는지 모르겠지만 아무튼 점화식은 맨 아래처럼 만들 수 있다 #include..

https://www.acmicpc.net/problem/1912 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net dp배열은 자신의 값으로 초기화해준다 그리고 자신의 왼쪽 dp배열에 자신의 합을더한것 과 자신의 dp배열의 크기를 비교해서 큰 값을 넣어준다 #include using namespace std; int n; int dp[100001] = {0}, a[100001] ={0}; int main(void) { cin >> n; for(int i=1; i> a[i]; dp[i] = a[i]; } for(int i=..

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 일단 아이디어는 수열 중 하나를 기준으로 잡고 왼쪽으로는 가장 긴 증가하는 부분수열, 오른쪽으로는 가장 긴 감소하는 부분수열을 계산하려고 했다 동시에 하려다 보니 복잡했는데 따로따로 구해서 더해도 똑같다는 생각이 들어서 그렇게 구현했다 포인트는 두 수열에 모두 자신이 포함되다보니 마지막에 1을 빼줘야한다는 것이다 #include using namespace std; int n; int lis[1001] = {0},l..

https://www.acmicpc.net/problem/11722 11722번: 가장 긴 감소하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10} www.acmicpc.net for문을 반대로 쓰는게 살짝 헷갈렸는데 가장 긴 증가하는 부분수열이랑 똑같이 풀어주면 된다 #include using namespace std; int n; int dp[1001] = {0}, a[1001] ={0}; int main(void) { cin >> n; for(int i=1; i> a[i]; dp[i] = 1..