3연DP. www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 이경우에는 1차원으로 비벼보려했는데 걍 2차원하는게 편할거같다 dp[2][123456]으로 만들어주고 dp[i][j]는 (i,j)에 있는 스티커를 땔때의 최대값이 된다. 여기서 조심해야할 점은 단순히 W나 M같은 꼴로만 탐색한다는 것이 아닌데, 이는 문제의 예시케이스에서도 볼 수 있듯이 체스의 나이트같은 위치에서도 최댓값을 가질 수 있다. 이것만 신경써주면 무난하게 AC. + 세그폴트가 안..
DP수련문제이다. www.acmicpc.net/problem/11052 11052번: 카드 구매하기 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net dp[i] 는 카드를 i개 구매할때의 금액의 최대값으로 설계했다. 최종답안은 당연히도 N개의 카드를 구매할때의 최대값이니 dp[n]을 출력해주면 AC. #include int max(int a, int b){ return a>b?a:b; } int dp[1234] = {0}; int input[1234] = {0}; int main(){ int n; int tmp = 0; scanf("%d", &n)..
www.acmicpc.net/problem/11724 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net 간단한 DFS 문제 무방향 그래프를 입력을 통해 만들어주고, 그 뒤에 dfs나 bfs 아무거나 하나 골라서 탐색해준다음 갯수만 세주면 된다. 나는 귀찮은관계로 클래식하게 재귀를 이용한 탐색을 사용했다. #include #include #include using namespace std; vector v[1001]; int visit[1001] = {..
www.acmicpc.net/problem/20309 20309번: 트리플 소트 $N$은 $3, 4, 5$ 중 하나이다. www.acmicpc.net 생각의 전환 이 문제를 풀기위해서 반드시 사고해야할 점은 "세개를 동시에 뒤집는 것" 이 무엇을 의미하는지 알아야한다 세개를 동시에 뒤집게 되면 세개 중 가운데에 있는 수는 항상 제자리에 있게 되고, 결과적으로 보자면 i 번째 수를 i+2번과 바꾸는것과 같게 되어서 홀수자리는 홀수자리끼리만 / 짝수자리는 짝수자리끼리만 바꿀수 있게 됩니다. 따라서 홀수자리에 짝수가 나온다면 절대 바꿀수 없으므로 NO, 아니면 YES를 출력하게 짜주면 됩니다. #include int arr[345678] = {0}; int main(){ int n; bool ans = tru..
https://www.acmicpc.net/problem/8464 8464번: Non-Squarefree Numbers Your program should output one integer, the n-th non-squarefree number. www.acmicpc.net 1577번의 정확히 정 반대에 해당하는 문제. 조금만 수정해줘도 쉽게 AC를 받을 수 있다. --- 소스코드 내립니다 --- setup이나 f함수의 역할은 같고, 기존의 f 함수는 k 이하의 squarefree number의 수를 세기 때문에, mid - f(mid)를 통해서 mid 이하의 non-squarefree number의 수를 세줄 수 있다. 그리고 탐색범위가 k의 영향에서 벗어나는지 WA가 나와서 그냥 e에 엄청 큰 수 ..
https://www.acmicpc.net/problem/1557 1557번: 제곱 ㄴㄴ 어떤수 N이 1이 아닌 제곱수로 나누어지지 않을 때, 이 수를 제곱ㄴㄴ수라고 한다. 제곱수는 4, 9, 16, 25와 같은 것이고, 제곱ㄴㄴ수는 1, 2, 3, 5, 6, 7, 10, 11, 13, ...과 같은 수이다. K가 주어졌을 때, K www.acmicpc.net 생각하는데 오래걸린 문제 처음에 위의 사진처럼 엄청 무식하게 접근했다가 조언을 받아서 뫼비우스 함수라는 걸 이용해서 문제를 해결했다. 인터넷에서 찾은 분이신데, 뫼비우스 함수를 코드와 함께 깔끔하게 정리해주셨다. https://ohgym.tistory.com/19 포함과 배제, 그리고 뫼비우스 함수 INTRO 적당히 꼼수를 써가면서 풀었는데 수학적..