수학6 [백준 1339] 단어 수학 www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 백트래킹 문제여서 백트래킹으로 풀었더니 답은 맞았지만 엄청나게 시간이 오래 걸렸다. 아래 제출한 기록이 백트래킹으로 풀었을 때 걸리는 시간이다. 백트래킹 로직은 1. 사용된 모든 알파벳을 담은 후 2. 각 알파벳에 숫자를 매칭시켜서 (백트래킹) 3. 최댓값을 구한 것이다. #include #include #include #include using namespace std; vector v(11); int .. 2021. 2. 9. [백준 1790] 수 이어쓰기2 www.acmicpc.net/problem/1790 1790번: 수 이어 쓰기 2 첫째 줄에 N(1 ≤ N ≤ 100,000,000)과, k(1 ≤ k ≤ 1,000,000,000)가 주어진다. N과 k 사이에는 공백이 하나 이상 있다. www.acmicpc.net 이분탐색이라고 되어있는데 이분탐색보다는 수학적 접근이 더 쉬운 것 같다. n까지 써있는 수열에서 k번째 수를 찾는 문제이다. 예시에선 n=20 k=23인데 직접 찾아보자 1. 1~9까지 숫자(한 자리수) = 총 9개 23 -= 9 k = 14가 된다. 2. 10 ~ 99까지의 숫자(두자리수) = 총 90개(100-10) 14 < 90이다. 따라서 k는 두자리수 어딘가에 위치한 다는 의미이다. 14는 두자리수이므로 /2하면 7이 나온다. 23은.. 2021. 2. 1. [백준 17451] 평행 우주 www.acmicpc.net/problem/17451 17451번: 평행 우주 행성 1에 가기 위해 필요한 것보다 세 배의 속도로, 행성 2의 경우 두 배의 속도로 이동하면, 지구에서는 900의 속도만 쌓으면 된다. www.acmicpc.net 카테고리가 이분탐색이긴 한데 잘 모르겠다.. 풀이 방법은 뒤에서 부터 순회하며 값을 찾는다. 현재의 값의 배수면서 && 이전 값보다 큰 최솟값을 찾는다. #include using namespace std; int n; int arr[300001]; int main(void) { scanf("%d", &n); for (int i = 0; i < n; i++) { scanf("%d", &arr[i]); } long long res = arr[n - 1]; for (.. 2020. 12. 27. [백준 11051] 이항 계수 2 www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 이항계수를 구하는 문제이다. nCk = n!/k!(n-k)!이지만 n과 k가 1000까지 입력을 받기 때문에 저 식대로 계산하면 오버플로우가 발생한다. 그래서 파스칼의 삼각형을 사용하여 구해준다. 파스칼의 삼각형은 dp를 사용해서 구한다. nCk = dp[i][j] if j=0 or i=j then 1 else dp[i][j] = dp[i-1][j-1] + dp[i-1][j]로 식을 세울 수 있다. #include using namespace std; int dp[1001][100.. 2020. 12. 23. 이전 1 2 다음
