hwooo

https://www.acmicpc.net/problem/4779 4779번: 칸토어 집합 칸토어 집합은 0과 1사이의 실수로 이루어진 집합으로, 구간 [0, 1]에서 시작해서 각 구간을 3등분하여 가운데 구간을 반복적으로 제외하는 방식으로 만든다. 전체 집합이 유한이라고 가정하고, www.acmicpc.net 풀이 문자열을 재귀로 넘겨 길이가 1보다 클 경우 3등분해서 1, 3번째는 다시 재귀를 실행하고 가운데 부분은 공백으로 바꾸어 처리했다. 코드 #include #include #include using namespace std; bool dash[540000]; void Blank(int n, int start) { if (n > 1) { n /= 3; Blank(n, start); for (in..

https://www.acmicpc.net/problem/24313 24313번: 알고리즘 수업 - 점근적 표기 1 f(n) = 7n + 7, g(n) = n, c = 8, n0 = 1이다. f(1) = 14, c × g(1) = 8이므로 O(n) 정의를 만족하지 못한다. www.acmicpc.net 풀이 주어진 문제는 a1*n+a0 >= c*n 이므로 이를 정리하면 (c-a1)*n >= a0가 된다. 이 때 a0, a1은 음수가 될 수 있다. 1. c-a1>0일 때 : (c-a1)*n >= a0 를 만족하면 O(n)의 정의를 만족한다. 2. c-a1= 0 : (음수) >= (양수)의 형태가 되므로 어느 경우에도 만족하지 못한다. - a0 = (음수)이므로 이는 (양수) > 따라서 ..

https://www.acmicpc.net/problem/25192 25192번: 인사성 밝은 곰곰이 첫번째 새로운 사람이 들어온 뒤 pjshwa, chansol, chogahui05은 모두 곰곰티콘으로 인사했다. 두번째 새로운 사람이 들어온 뒤 pjshwa와 chansol은 다시 곰곰티콘으로 인사했다. www.acmicpc.net 풀이 set을 사용하여 중복된 인원은 저장하지 않았다. 이 때 ENTER 값 입력 시 set에 있던 사람의 수를 세고 set을 초기화하여 인사한 인원의 수를 다시 세었다. 코드 #include #include #include #include using namespace std; set name; int main() { int N, cnt = 0; string S; scanf(..

https://www.acmicpc.net/problem/11057 11057번: 오르막 수 오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다. 예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다. 수 www.acmicpc.net 풀이 각 자리수마다 끝나는 숫자가 무엇인지에 따라 DP 배열을 만들었다. - 한 자리 수는 1, 2, 3, ... , 9로 하나씩 밖에 없다. - 수는 0으로 시작할 수 있으므로 각 자리수마다 0으로 끝나는 수는 0, 00, 000, ... 으로 각 자리수마다 1개씩이다. - 길이가 i이고 j로 끝나는 오르막 수의 개수는 길이가 i-1일 때 0~j까지 끝나는 수..

https://www.acmicpc.net/problem/2096 2096번: 내려가기 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 숫자가 세 개씩 주어진다. 숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다. www.acmicpc.net 풀이 총 30만 칸에 최소, 최대값을 포함한 DP 배열을 만들어 i 번째 칸에 도착했을 때의 최소, 최대값을 저장했다. 처음엔 DP 배열과 값을 받는 배열 2개를 생성했으나 이렇게 할 경우 메모리가 초과되어 초기값을 DP 배열에 저장하고, 값을 더해가는 방식을 사용했다. 코드 #include #include using namespace std; int DP[100000][3][2]; int Get(int a, ..

https://www.acmicpc.net/problem/2502 2502번: 떡 먹는 호랑이 첫줄에 첫 날에 준 떡의 개수 A를 출력하고 그 다음 둘째 줄에는 둘째 날에 준 떡의 개수 B를 출력한다. 이 문제에서 주어진 D, K에 대해서는 항상 정수 A, B (1≤ A ≤ B)가 존재한다. www.acmicpc.net 풀이 D인 날짜에 넘긴 떡의 개수를 첫째, 둘째 날에 넘긴 떡의 개수로 표현하기 위해 2차원 DP 배열을 세웠다. 이 문제에서 A는 항상 1이상의 자연수이므로 A의 초기값을 1로 설정하고 값을 1씩 증가시키며 DP[D][0]*A+DP[D][1]*B=K가 되는 값을 구했다. 코드 #include using namespace std; int DP[31][2]; int main() { int ..

https://www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 풀이 0-1배낭문제에서 팩을 중복 사용할 수 있다고 생각하고 풀었다. 먼저 DP[카드 팩의 개수(i)][총 개수(j)]으로 구성된 2차원 배열을 생성하고, 팩 1의 값은 팩의 가격*개수로 구했다. 팩 i의 카드 개수(i)가 총 개수(j)보다 - 많을 경우 : 팩 i-1까지 선택한 경우(DP[i-1][j])의 값이 들어갈 수 밖에 없다. - 적을 경우 : j개 모두 팩 i-1까지 선택한 경우(DP[i-1]..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 풀이 배낭의 무게가 K일 때 i번째 물품을 넣을 수 있는지를 판단하며 계산하였다 DP[물건][배낭무게]로 설정하여 DP[i][j] 값은 - i번째 물건이 배낭 무게보다 무거울 경우 : 배낭에 넣지 못하므로 DP[i-1번째 물건][배낭 무게] - i번째 물건을 넣을 수 있는 경우 : 같은 무게일 때 i-1번째 물건을 넣었을 경우와, ..