문제_링크 9466번: 텀 프로젝트 이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 www.acmicpc.net 자세한 설명은 생략한다. ( 설명과 관련해서는 다른 사람이 더 잘해둔 게 많아서 내가 참고한 블로그 링크를 아래에 적어두겠다. ) 참고_링크 일단 80%에서 시간 초과가 난 코드이다. 시간 복잡도를 O(N)으로 짠 것 같다고 생각했는데 문제가 발생했다. #include #include #include using namespace std; int students[100002]; bool visited[100002]; int checkNum[100002]; /..

문제_링크 7785번: 회사에 있는 사람 첫째 줄에 로그에 기록된 출입 기록의 수 n이 주어진다. (2 ≤ n ≤ 106) 다음 n개의 줄에는 출입 기록이 순서대로 주어지며, 각 사람의 이름이 주어지고 "enter"나 "leave"가 주어진다. "enter"인 경우는 www.acmicpc.net set또는 map을 사용하는 문제다. #include #include using namespace std; set enterMember; int main() { int n; string inputName, command; cin >> n; for (int i = 0; i > inputName >> command; if (command == "enter") { enterMember.i..

문제 링크 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 이분 탐색 문제다. 간단하게 나무를 자르는 값을 left = 1, right = 가장 긴 나무의 길이로 해서 이분 탐색을 이용해 값을 구하면 된다. 이분 탐색을 해서 나무를 자르는 값으로 나무를 잘랐을 때 잘려나간 나무의 값이 현재 필요한 나무의 값과 같으면 값을 출력하면 된다. 주의할 점은 이 부분인데, 만약 같은 경우가 없을 경우에 나오면 계산된 값이 현재 필요한 나무의 값보다 작으면 나무를 자르는 길이값을 ..

DP 문제이다. 전에 풀다가 어려워서 포기했었는데 이전 문제에서 DP도 풀었겠다. 재도전해보았고, 결국 해결했다. ( 40분 정도 소요 ) #include #include #include using namespace std; int HousePaintCost[1001][4]; int DP[1001][3][3]; // 1000, 현재값 - 0, 1, 2, 시작값 - 0, 1, 2 int main() { int houseCnt; cin >> houseCnt; memset(DP, 0x3f, sizeof(DP)); for (int i = 0; i R >> ..

DP 문제이다. 그냥 DP를 활용해서 전부 값을 찾았더니 해결되었다. #include #include #include #include using namespace std; const int MaxVal = 50000000; int DP[100001][5][5] {}; //until 100000 | left 1,2,3,4 | right 1,2,3,4 int CalcCost(int start, int end) { if (start == end) return 1; else if (start == 0) return 2; else if (start % 2 == 0) { if (end % 2 == 1) return 3; else return 4; } else if (start % 2 == 1) { if (end %..

일단 문제를 풀어보기로 했다. 일단 한 번 코드를 작성해보았는데, 문제가 많았다. #include #include using namespace std; struct Gem { public: Gem() : weight(0), price(0) {}; Gem(int weight, int price) : weight(weight), price(price) { }; ~Gem() {}; public: int weight; int price; bool operator>(const Gem& gem) { return price > gem.price; } }; Gem gems[300000]; int bagWeight[300000];//가방에 담을 수 있는 최대 무게 bool visited[300000]; int gemCn..