코딩스토리

https://www.acmicpc.net/problem/1135 1135번: 뉴스 전하기 민식이는 회사의 매니저이다. 그리고, 민식이는 회사의 중요한 뉴스를 모든 직원에게 빠르게 전달하려고 한다. 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다 www.acmicpc.net 문제 요약 - 민식이의 회사는 트리 구조이다. 모든 직원은 정확하게 한 명의 직속 상사가 있다. - 모든 직원은 민식이의 직접 또는 간접적인 부하이다. (루트 = 민식) - 1분에 한 사람씩에게만 뉴스를 전파할 수 있음 - 모든 직원이 뉴스를 접하게 되는 최소 시간을 구하라 해결 처음에는 자식 노드가 많은 직원부터 소식을 전파하면 되지 않을까 생각해봤는데 조금만 더 고민해보면 당연히 그렇지 않다는 것을..

www.acmicpc.net/problem/16120 16120번: PPAP 첫 번째 줄에 문자열이 주어진다. 문자열은 대문자 알파벳 P와 A로만 이루어져 있으며, 문자열의 길이는 1 이상 1,000,000 이하이다. www.acmicpc.net 그리디 알고리즘이라길래 풀었다가 크게 당한 문제다.. 그리디 문제를 여러 번 풀수록 내 멍청함에 한 번 감탄하고 내가 풀이법을 떠올리는 것에 또 한 번 감탄한다. 참 신기한 알고리즘이야.. 이거 풀려고 연습장에 PPAP를 몇 번을 썼는지 모르겠다ㅋㅋ 처음에 접근을 완전히 이상하게 해서 너무 많은 시간을 버리고 결국 코드를 처음부터 다시 짰다. 먼저 정답을 받은 방법부터 설명하자면 아래와 같다. 1. 문자열의 마지막부터 시작하여 하나의 문자씩 확인한다 (딱 봐도 ..

www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 코드포스 만년 초록 따리를 벗어나기 위해 그리디 문제를 많이 풀어봐야겠다고 마음먹었다. 이 문제의 풀이는 다음과 같다. 1. 모든 단어에서 각 문자가 얼마만큼의 계수를 갖는지를 구하기 ex) AB이면 10A + B, 즉 A = 10, B = 1을 저장 2. 계수가 큰 알파벳 순으로 정렬 (어차피 전체 단어의 합이기 때문에 계수가 크면 큰 수를 할당해야 한다.) 3. 정렬된 알파벳에 9부터 순서대로 할당하여..