분류 전체보기
-
[백준] 패션왕 신해빈 - 9375번알고리즘 문제 풀이/백준 2021. 3. 2. 21:39
문제설명 www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 기본아이디어 옷들의 종류별로 그 종류의 옷을 고를 수 있는 경우의 수가 주어지므로 옷들의 종류별 (갯수+1)들의 곱을 구하면 모든 경우의 수를 구할 수 있다.(옷을 안고르는 경우도 포함하므로) 그리고 모든 옷을 안 입는 경우 하나를 빼면 정답이 나올 것이다. 구현코드 1 2 3 4 5 6 7 8 9 10 11 ..
-
[백준] 수들의 합 2 - 2003번알고리즘 문제 풀이/백준 2021. 3. 1. 14:54
문제설명 www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 기본아이디어 문제를 읽고 처음 시도해본 아이디어는 재귀를 이용해서 풀어보는 것 이었습니다. 각 배열의 인덱스에서 현재 경우에서 이전까지의 합을 받아와서 배열에서 인덱스에 해당하는 값을 더하는 경우, 더하지 않는 경우를 각각 재귀로 하면 모든 경우를 고려할 수 있다고 생각했습니다. 결과는 시간초과, 다시 한번 문제를 읽어보니 N, M의 범위가 엄청 큽니다. 특히 ..
-
[백준] 토너먼트 - 1057번알고리즘 문제 풀이/백준 2021. 3. 1. 13:29
문제설명 www.acmicpc.net/problem/1057 1057번: 토너먼트 김지민은 N명이 참가하는 스타 토너먼트에 진출했다. 토너먼트는 다음과 같이 진행된다. 일단 N명의 참가자는 번호가 1번부터 N번까지 배정받는다. 그러고 난 후에 서로 인접한 번호끼리 스타를 www.acmicpc.net 기본아이디어 문제를 보고 첫 생각은 1차전이 끝나면 2차전은 참가자가 반으로 줄겠다는 생각이 들었습니다. 그래서 한 참가자가 우승을 하려면 log N(밑은 2) 번의 경기를 치뤄야 겠다는 생각도 했습니다. 그리고 토너먼트 상대는 홀, 짝으로 구성이 되고 이긴 사람이 새롭게 받는 번호는 홀수인 경우는 (X + 1) / 2 짝수인 경우는 X / 2 입니다. 찾아낸 이러한 규칙을 토대로 김선수와 임선수의 번호가 바..
-
[백준] 링 - 3036번알고리즘 문제 풀이/백준 2021. 3. 1. 13:02
문제설명 www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 기본아이디어 문제를 읽고 12 / 3 -> 4 / 1, 12 / 8 -> 3 / 2 로 바꿔주는 작업이 필요하다고 생각이 들었고, 그때 필요한 두 값을 나누는 값은 두 값의 최대공약수라는 점을 파악했다. 그래서 두 값을 매개변수로 최대공약수를 리턴해주는 함수를 만들어서 사용했다. 알고리즘은 유클리드 호제법을 기반해서 만들어졌다. 결과는 성공! 구현코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19..
-
[백준] 에디터 - 1406번알고리즘 문제 풀이/백준 2021. 2. 28. 20:27
문제설명 www.acmicpc.net/problem/1406 1406번: 에디터 첫째 줄에는 초기에 편집기에 입력되어 있는 문자열이 주어진다. 이 문자열은 길이가 N이고, 영어 소문자로만 이루어져 있으며, 길이는 100,000을 넘지 않는다. 둘째 줄에는 입력할 명령어의 개수 www.acmicpc.net 기본아이디어 처음 문제를 보고 생각한 것은 List를 사용해서 한 글자씩 저장한 다음에 커서의 위치를 저장하는 변수를 하나 둬서 입력받은 명령어에 따라 커서를 이동시키고, 값을 삭제시키기고, 글자를 추가하는 방식을 생각했었다. 결과는 실패, 바로 시간초과가 발생했다. 시간초과가 발생하고 다시 처음 입력조건을 살펴보니 N, M이 상당히 크다는 것을 알 수 있었다. ArrayList 든 LinkedList이..