제목이 같은 날먹문제... 트리에 존재하는 모든 경로 중 가장 긴것의 길이를 찾으라하고 있다. dfs로 풀었다. 일단 가장 긴 경로는 반드시 리프노드 - 리프노드 간 길이일 것이다. 리프노드가 아닌 노드가 긴 경로가 된다면 그 노드의 자식노드로 더 긴 경로가 있을수밖에 없기 때문이다 ( 가중치의 길이가 음수가 될 수 없다 ) 처음 생각한것은 1을 기준으로 가장 긴 경로 & 두번째로 긴 경로 를 찾는 것인데, 중복문제도 있고, 그림에서처럼 1을 지나지 않는 가장 긴 경로도 있기에 일단 루트노드에서 가장 긴 경로를 찾고, 그 경로에서 나온 리프노드를 시작점으로하는 가장 긴 경로를 찾아주었다. 루트노드에서 가장 긴 경로와 실제 가장 긴 경로가 1 ) 하나도 겹치지 않는다면 조건에 모순이 생기고, 2 ) 겹친다..

약간의 두뇌가 가미된 배낭문제 기본적인 구조는 12865번 평범한 배낭과 동일하다. www.acmicpc.net/problem/12920 12920번: 평범한 배낭 2 첫 번째 줄에 N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 10,000) 이 빈칸을 구분으로 주어진다. N은 민호의 집에 있는 물건의 종류의 수이고 M은 민호가 들 수 있는 가방의 최대 무게다. 두 번째 줄부터 N개의 줄에 www.acmicpc.net 먼저 딱 보고 생각한 것은 O(KNM)인데, 이렇게 되면 당연하겠지만 TLE가 나온다. O(KNM)은 N개의 물건에 대해서 1~K갯수가 있을텐데, 각각의 개수를 모두 "K배 더 무겁고 K배 가치가 더 나가는 물건" 으로 바꿔주면 쉽게 나온다. AC는 O(NlogKM) 으로 받았는데, K를..

말 그대로 평범한 배낭 문제... 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 0/1 배낭 문제이다. dp[i][j] 를 i번째까지 살펴본 배낭의 용량이 j일때의 최대 가치 로 정의하면 풀수 있다. 이 최대 가치를 만드는법은 크게 세가지 경우로 나뉘는데 1) 배낭에 i번째를 넣을수 있고, 넣었음. ( dp[i][j] = dp[i-1][j-w[i]] + v[i] ) 2) 배낭에 i번째를 넣을..

의외로 골드V에 날먹이 많구만 아주 좋다. www.acmicpc.net/problem/17828 느낌표를 출력해야 하는 경우는 단 두가지밖에 없다. 1 ) ZZZZZZ와 같이 길이가 N일때의 가치를 최대로 해도 X에 미치지 못하는 경우 2 ) N일때의 가치를 최소로 해도 X보다 커지는 경우 각각 n*26 x 라는 수식을 통해 판별해줄 수 있다. 사전순으로 앞서는 문자열을 만들기위해서는 다른건 다 무시하더라도 앞에 오는 A의 개수가 가장 많아지면 될 것이다. 그렇기에 최대한 타이트한 선까지 A를 출력하고, A와 Z 사이에 "단 한글자만" 남는 가치를 매꾸고, 남은 모든 길이를 Z로 출력해주면 사전순으로 가장 앞서는 문자열이 만들어지게 된다. 더보기 #include using namespa..

www.acmicpc.net/problem/1038 1038번: 감소하는 수 음이 아닌 정수 X의 자릿수가 가장 큰 자릿수부터 작은 자릿수까지 감소한다면, 그 수를 감소하는 수라고 한다. 예를 들어, 321과 950은 감소하는 수지만, 322와 958은 아니다. N번째 감소하는 수를 www.acmicpc.net 브루트포싱. 처음 보고 든 생각은 그냥 최대값까지 for문 돌리면서 감소하는 수들을 벡터에 담는 것이었는데, 이렇게 하자니 TLE가 나올것이 눈에 보여서 다른 방법으로 접근해보도록 했다. 가장 큰 감소하는 수는 9876543210일것이고, 가장 작은 감소하는 수는 0이 된다. 감소하는 수들의 특징은 수들의 정렬 순서가 내림차순으로 일정하다는 것인데, 확률과통계를 배우는 고딩들은 알겠지만 정렬 순서..

시험기간인데..... 참고참다가 결국 폭팔했다. 나의 PS를 시험이 막을수는 없지. https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나� www.acmicpc.net 처음 보고 떠오른게 숫자의 자릿수를 일정하게끔 뒤에 0을 붙여서 계산해주는것이었다. 그런데 0을 붙이고 제출을 하자 WA가 나왔었고, 질문검색 란에 반례가 있었다. 2 98 988 으로 입력이 들어온다면 내 소스는 98898을 출력했었다. 이걸 해결하기 위해서 고민해본 결과, 9..