Jubil의 프로그래밍 블로그

2750_수 정렬하기 링크 https://www.acmicpc.net/problem/2750 풀이 수를 오름차순으로 정렬하면 됩니다. N은 1

9251_LCS 링크 https://www.acmicpc.net/problem/9251 풀이 처음에 편의를 위해서 0행과 0열을 0으로 세팅해줍니다. DP[i][j]를 LCS(i까지의 string2, j까지의 string1)라고 정의합시다. LCS로 비교하는 string의 마지막 문자가 같다면, LCS(i까지의 string2, j까지의 string1) = LCS(i-1까지의 string2, j-1까지의 string1) + 1이 됩니다. 즉, if(string2[i] == string1[j]) DP[i][j] = DP[i-1][j-1] + 1이 됩니다. LCS로 비교하는 string의 마지막 문자가 다르다면, LCS(i까지의 string2, j까지의 string1) = max(LCS(i-1까지의 strin..

2018 선린인터넷 고등학교 모의해킹 방어대회에서 2위를 하여 은상을 받았습니다. 처음으로 동, 장려상이 아닌 은상을 받게 되어 기쁩니다!!

2156_포도주 시식 링크 https://www.acmicpc.net/problem/2156 풀이1 A[i]를 i번째 포도주의 양, DP[N][L]을 N번째 마신 포도주의 양, 연속 L번째라고 정의하겠습니다. 우선 i번째에 0번 연속으로 먹는다(이번에 먹지 않는다)고 했을 때, DP[i][0]을 정의할 수 있습니다. 이번에 먹지 않으니 변화가 없다는 뜻입니다. 그리고 전에 먹었는지 먹지 않았는지는 상관하지 않기 때문에 전 단계에서 먹은 양 중에 최대로 먹은 양을 가져오면 됩니다. DP[i][0] = max(DP[i-1][0], DP[i-1][1], DP[i-1][2]) 1번 연속으로 먹는다(이번에 먹고 전 단계에서 먹지 않았다)고 했을 때, DP[i][1]을 정의할 수 있습니다. 이번에 먹으니 A[i]를..

1463_1로 만들기 링크 https://www.acmicpc.net/problem/1463 풀이 우선 DP[N]을 정수 N을 1로 만드는 데 필요한 최소 연산 횟수라고 정의합시다. N은 N-1에서 1을 더해 만들 수 있고, N/2에서 2를 곱해 만들 수 있고, N/3에서 3을 곱해 만들 수 있습니다. DP[N]은 DP[N-1]과 DP[N/2]와 DP[N/3]에서 한 번의 연산을 더 수행해서 만들 수 있습니다. 하지만 DP[N]은 최소 연산 횟수이기 때문에, DP[N] = min(DP[N-1]+1, DP[N/2]+1, DP[N/3]+1) 라는 식이 생깁니다. 이걸 조건마다 코드로 구현하면 됩니다. 코드

[Codegate 2016] watermelon 32bit 바이너리이고, Canary와 NX가 걸려있습니다. 바이너리를 실행하면 우선 이름을 입력 받습니다. 그 후 옵션을 입력 받네요. 이름을 scanf %s 입력 제한 없이 bss 영역에 받고 있네요. 원할 때 가져올 수 있는 부분이니 생각해 둡시다. 그 뒤로는 4294967295 -> -1이 있고, 순서대로 1일 때 Add, 2일 때 View, 3일 때 Modify입니다. -1일 때는 어떤 역할을 할까요? 암호화를 해줍니다… 이름을 변경해주고 Add부터 봅시다. music과 artist를 추가할 수 있습니다. main에서 봤던 저 친구가 playlist에 몇 개의 음악이 있는지 나타내는 count이고, v1이 playlist를 저장하는 공간이었네요! ..

11052_붕어빵 판매하기 링크 https://www.acmicpc.net/problem/11052 풀이 붕어빵을 N개 팔아서 얻을 수 있는 최대 이익을 DP[N]이라고 정의하고, 붕어빵 N개 팔 때의 가격을 P[N]이라고 정의하겠습니다. 그리고 DP는 모두 0으로 초기화 하겠습니다. 위의 1 5 6 7 의 예제로 설명하겠습니다. 붕어빵 1개를 팔아야 한다면 D[1-1] + P[1] 하나뿐입니다. 참고로 DP[1-1] + P[1]은 1-1개 팔 때 최대 이익 + 1개 팔 때의 가격입니다. 붕어빵 2개를 팔아야 한다면 DP[2-1] + P[1] DP[2-2] + P[2] 중에 큰 값이 DP[2]가 될 것입니다. DP[2-1] + P[1]은 1+1=2고, DP[2-2] + P[2]는 0+5=5입니다. DP[..

오르막 수는 계단 수와 유사합니다.그 다음 수를 가기 위한 조건이 있기 때문에 마지막 자리를 저장해줘야 합니다. DP[N][10] 이렇게 선언해주면 0~9의 마지막 숫자를 저장해 줄 수 있습니다.그리고 0으로 시작할 수 있기 때문에 DP[1][0~9]를 모두 1로 초기화 합니다. 마지막 자리가 0이라면 0~9까지의 숫자가 뒤에 올 수 있습니다.DP[N][0~9] += DP[N-1][0] 마지막 자리가 1이라면 1~9까지의 숫자가 뒤에 올 수 있습니다.DP[N][1~9] += DP[N-1][1] ... 마지막 자리가 9라면 9만 뒤에 올 수 있습니다.DP[N][9] += DP[N-1][9] 그럼 i는 2부터 n까지, j는 0부터 9까지, k는 j부터 9까지 3중 for문을 돌리면 됩니다.DP[i][k] +..

1912_연속합 링크 https://www.acmicpc.net/problem/1912 풀이 간단하게 풀 수 있는 문제입니다. 우선 가장 큰 값을 구해야 하기 때문에 max를 선언합니다. 연속합의 최댓값의 최솟값(-1000)-1로 초기화 합니다. DP 배열에 값을 입력 받고, i=1부터 n까지 for문을 돌립니다. 그리고 DP[i] = MAX(DP[i], DP[i-1] + DP[i])를 해줍니다. 굳이 전의 연속합과 더한 것보다 이번 숫자가 크면 더할 필요가 없기 때문입니다. 연속해서 더한 게 크다면 더해야죠. 대신에 그 다음 라인에 max = MAX(max, DP[n])로 max 값을 구해주는 일도 잊지 말아야 합니다. 코드

2193_이친수 링크 https://www.acmicpc.net/problem/2193 풀이 조건을 보면 0으로 시작하지 않고, 1이 연속으로 올 수 없습니다. 그럼 마지막 자리(0, 1)를 담을 수 있는 DP[N][2]를 만든다고 가정합시다. N이 1이면 0이 올 수 없으므로 DP[1][0] = 0, DP[1][1] = 1이 됩니다. 그리고 0으로 올 수 있는 건 마지막 자리가 0과 1 다 가능하고, 1로 올 수 있는 건 마지막 자리가 0인 경우 밖에 없습니다. 이 조건을 이용해서 점화식을 정의해 보겠습니다. DP[N][0] = DP[N-1][0] + DP[N-1][1] DP[N][1] = DP[N-1][0] 입니다. 이렇게 코드를 짜고 마지막에 DP[N][0] + DP[N][1]을 출력하면 됩니다. ..