왕도를 찾아서

https://www.acmicpc.net/problem/26156 26156번: 나락도 락이다 NAROCK, NAROCK, NAROCK, NAROCK 총 4개이다. www.acmicpc.net 나락도 락이다. 부모님께 온 연락도 락이다. 오락가락?도 락? 이다.? 일단은 입력받은 문자열의 부분열 중 ROCK의 개수가 몇개 있는지 찾아줘야 한다는 문제이다. STEP 0. 문자열 S의 부분열 중 "K"이 몇개 있는지 찾는다. 이를 이용해 S의 부분열 중 "CK"이 몇 개 있는지 찾을 수 있고, 이를 이용해 S의 부분열 중 "OCK"이 몇 개 있는지 찾을 수 있고, 이를 이용해 S의 부분열 중 "ROCK"이 몇 개 있는지 찾을 수 있다. S를 i번째 이후 문자부터만 셌을 때 부분열 중 문자열 "K"가 몇 개..

https://www.acmicpc.net/problem/11390 11390번: 맛있는 과자 첫 번째 줄에 네 개의 자연수 a, b, N, K (1 ≤ a, b ≤ 100, 1 ≤ N ≤ 40, 1 ≤ K ≤ 2N)이 공백을 사이로 두고 주어진다. www.acmicpc.net DP문제를 돌다가 발견했는데 알고보니 그냥 수학문제. DP인 이유는 조합을 이용하기 때문이다. STEP 0. DP를 이용해 nCk (조합, Combination) 값들을 전부 배열 co[n][k]에 저장해준다. STEP 1. 두 삼각형의 넓이비는 a^2 : b^2. 왜 그런지는 중학교 때 배운다. a와 b를 입력받는데, a가 b보다 더 큰 값이라고 가정해보자. 어차피 입력받은 뒤 작은 게 a가 되도록 수정하면 되니 상관 X. A=..

https://www.acmicpc.net/problem/19847 19847번: 여우 신탁 “여우신님, 여우신님, 번호 하나만 내려 주세요…” 누구나 1 이상 45 이하의 정수 여섯 개를 잘 골라서 인생이 달라지거나, 혹은 1 이상 10,000 이하의 정수 하나를 잘 골라서 맞았습니다!!를 받는 www.acmicpc.net 예를 들어 일단 첫 여우는 9개의 수 중 하나를 달라고 할 것이다. 그러면 9개의 숫자들이 나올 확률은 전부 같다. 즉, 각 숫자가 뽑히는 경우의 수를 저장한 배열은 int p[]={1,1,1,1,1,1,1,1,1}; 로 나타낼 수 있다. STEP 0. 입력 두 번째 줄에 받는 숫자들이 예를 들어 9 4 2 라면 여우신은 4 이상 수들은 전부 4로 나눈 나머지를 계산해야 하고, 또 ..

https://www.acmicpc.net/problem/1955 1955번: 수식 표현 수식 표현이란 1, +, *, !, (, )로만 이루어진 수식을 말한다. 간명하게 정의하기 위해, 다음과 같이 귀납적으로 정의할 수 있다. 1은 수식표현이다. e가 수식표현이면 (e)와 e!도 수식표현이다. e1과 e2 www.acmicpc.net 시간복잡도: n이 10000 이하이기 때문에 O(n^2) 안에 풀 수 있어야 한다. PART 0. 입력이 i일때 출력해야할 값을 dp[i]라고 두면 일단 dp[0]~dp[8] 값을 생각해보자면 dp[0] = 0; dp[1] = 1; dp[2] = 2; dp[3] = 3; dp[4] = 4; dp[5] = 5; dp[6] = 3; dp[7] = 4; dp[8] = 5; PA..