![]()
문제https://www.acmicpc.net/problem/2211 풀이1. 1번 컴퓨터에서 각각의 컴퓨터까지 다익스트라를 이용해 최단 경로 구하기-> 이 부분에서 처음에 문제를 읽고 '경루의 개수가 최소여야한다'는 말 때문에 헷갈렸으나, 원래 연결된 경로에서의 최소 시간 보다 크면 안된다는 말, 즉 최소 cost를 그대로 유지해야 한다는 말이 추가로 있기 때문에, 다익스트라로 최소 비용이 드는 루트들만 남기면 되는거였다.2. 이때 1번 컴퓨터에서 각 노드까지의 루트를 저장해둔다.-> 2차원 배열 route를 사용하여 저장해줬다.3. 2에서 저장해둔 루트를 중복 없이 출력한다.-> route 배열을 2중 for문으로 돌며 중복을 없애기 위해 pair자료형의 set인 finalRoute에 넣어줬다. 코..
문제 https://www.acmicpc.net/problem/1699 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다 www.acmicpc.net dp[idx] = n -> idx까지의 최대 연속합이 n이라는 의미이다. dp[제곱수]는 무조건 1이다. 따라서 처음엔 어떤 수던간에 dp[i] = dp[직전 제곱수] + dp[i-직전 제곱수] 즉 dp[i] = 1 + dp[i-직전 제곱수] 라는 공식을 세우고 풀었는데 틀렸다. 코드는 다음과 같았다. #include #include #include #..
문제 https://www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 처음에 문제를 보고 도통 어떻게 풀어야하는지 답이 안잡혔는데,, 질문 게시판을 잠깐 보고 아이디어를 얻어 바로 풀었다. 힌트는 다음과 같다. 뒤에 0이 붙는 개수를 구해야하는데, 0이 붙는다는 것은 10이 한번씩 곱해진다는 것이다. 10의 소인수는 2와 5인데, 보통 2는 5보다 소인수로 많이 가지므로, 곱해지는 5의 개수를 카운트하면 된다. #include #include #include #include #include #include #include #include #inc..
https://www.acmicpc.net/problem/4949 4949번: 균형잡힌 세상 하나 또는 여러줄에 걸쳐서 문자열이 주어진다. 각 문자열은 영문 알파벳, 공백, 소괄호("( )") 대괄호("[ ]")등으로 이루어져 있으며, 길이는 100글자보다 작거나 같다. 입력의 종료조건으로 맨 마 www.acmicpc.net #include #include #include #include #include #include #include #include #include #include #include using namespace std; //성공 string s; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); getline(cin, s); w..
문제 https://www.acmicpc.net/problem/10989 10989번: 수 정렬하기 3 첫째 줄에 수의 개수 N(1 ≤ N ≤ 10,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 10,000보다 작거나 같은 자연수이다. www.acmicpc.net 제한 메모리가 의도적으로 낮게 설정 되어있다. 처음엔 아무생각 없이 평소 하던대로 벡터에 입력 받고, sort함수로 정렬 후 출력했다. 당연히 결과는 메모리 초과. #include #include #include #include #include #include #include #include using namespace std; int n; vector v; int main() { ios_base::sync_w..
문제 https://www.acmicpc.net/problem/5635 5635번: 생일 어떤 반에 있는 학생들의 생일이 주어졌을 때, 가장 나이가 적은 사람과 가장 많은 사람을 구하는 프로그램을 작성하시오. www.acmicpc.net 풀이 #include #include #include #include #include #include #include #include #include #include using namespace std; int n, year, month, date; string name, youngest, oldest; vector nameVec; vector dateVec, monthVec; vector yearVec; //year, idx vector youngVec, oldVec,..
