전체 글
-
[1969] DNABOJ 2021. 12. 29. 04:31
https://www.acmicpc.net/problem/1969 1969번: DNA DNA란 어떤 유전물질을 구성하는 분자이다. 이 DNA는 서로 다른 4가지의 뉴클레오티드로 이루어져 있다(Adenine, Thymine, Guanine, Cytosine). 우리는 어떤 DNA의 물질을 표현할 때, 이 DNA를 이루는 뉴클레오 www.acmicpc.net 그때그때 가장 많이나온 문자를 그리디적으로 선택하면 된다. n개의 문자열을, m번에 걸쳐서 하나씩 순회하며 {A G C T} 각각의 개수중 최대를 tar에 저장해두었다면, 최종적인 거리를 구하기 위해서 (n-tar)를 누적합해 나가면 된다. 거리가 같은 문자열이 여러개인 경우, 사전순에 우선해야 한다는 조건이 있는데 string base="ACGT"; ..
-
[1913] 달팽이BOJ 2021. 12. 29. 04:00
https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net (n/2, n/2)에서 시작하는 경우에는 위->오른쪽->아래->왼쪽->위...처럼 방향이 돌아가며 방향이 바뀌지 않고, 방향을 유지하며 진행하는 횟수는 { 1 1 2 2 3 3 4 4 ...}의 순열을 따름을 이용해 구현하면 된다. 반대로 (0, 0)에서 시작하는 경우에는, 바로 위 방법에서 방향을 반대로 바꾸고 일단 진행하다, 맵을 벗어나거나 이미 탐색한 공간이 등장한 경우에는 방향을 바꾸어주면 ..
-
[17478] 재귀함수가 뭔가요?BOJ 2021. 12. 29. 01:32
https://www.acmicpc.net/problem/17478 17478번: 재귀함수가 뭔가요? 평소에 질문을 잘 받아주기로 유명한 중앙대학교의 JH 교수님은 학생들로부터 재귀함수가 무엇인지에 대하여 많은 질문을 받아왔다. 매번 질문을 잘 받아주셨던 JH 교수님이지만 그는 중앙대 www.acmicpc.net 재귀적으로 잘 출력하면 된다. 입력되는 n이 곧 최대 depth이고, depth*4개의 '_'를 출력해주어야 하는데, string base="____"처럼 '_' 4개를 넣어두고 d번 반복하여 base를 출력하여 구현해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35..
-
[11576] Base ConversionBOJ 2021. 12. 29. 00:36
https://www.acmicpc.net/problem/11576 11576번: Base Conversion 타임머신을 개발하는 정이는 오랜 노력 끝에 타임머신을 개발하는데 성공하였다. 미래가 궁금한 정이는 자신이 개발한 타임머신을 이용하여 500년 후의 세계로 여행을 떠나게 되었다. 500년 후의 www.acmicpc.net a진수를 b진수로 바꾸는 문제다. 처음에 a진수로 주어진 수를 10진수로 바꾸어주고, 이를 num에 넣어두면 v.push_back(num%b); num/=b; 위 과정을 num>0일동안 진행하면 작은 자리수부터 순차적으로 담기게 된다. 한번 reverse 해주거나, 반대로 순회( rbegin() -> rend() )하여 출력해주면 되겠다. 1 2 3 4 5 6 7 8 9 10 1..
-
[14908] 구두 수선공BOJ 2021. 12. 28. 00:29
https://www.acmicpc.net/problem/14908 14908번: 구두 수선공 최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답 www.acmicpc.net 일의 효율(우선순위)을 (s / t)=d로 놓은 뒤, d가 내림차순이 되도록 정렬한다. d가 같은 경우에는 idx가 오름차순이 되도록 한 뒤, 인덱스를 출력하면 되겠다. 이 문제에 적용된 "Exchange argument"에 대해서 설명한 좋은 글이 있으니, 이 문제를 풀때 참고해보면 좋겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 2..
-
[16496] 큰 수 만들기BOJ 2021. 12. 27. 04:17
https://www.acmicpc.net/problem/16496 16496번: 큰 수 만들기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 리스트에 포함된 수가 주어진다. 수는 공백으로 구분되어져 있고, 1,000,000,000보다 작거나 같은 음이 아닌 정수 이다. 0을 제외한 나 www.acmicpc.net n개의 수가 전부 0인경우 "000...000"이 결과에 담길 수 밖에 없으므로 이에대한 예외처리가 필요하다. 그 외에는 사전순으로 정렬해주고, 출력하면 되겠다. 정렬은 string의 +연산과 부등호로, 아래처럼 간단하게 구현할 수 있다. (string a, string b) return (a+b)>(b+a); 1 2 3 4 5 6 7 8 9 10 11 12 13..
-
[7570] 줄 세우기BOJ 2021. 12. 26. 19:44
https://www.acmicpc.net/problem/7570 7570번: 줄 세우기 입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하 www.acmicpc.net 단순 nlogn LIS인줄 알았는데, {1 3 4 2} 에서 한번에 {1 2 3 4}를 만들 방법이 없다. {1 3 4 2} -> {2 1 3 4} -> {1 2 3 4}처럼, 두번에 걸쳐서 이동해야 한다. 연속하는 수로 이루어진 LIS를 찾아주면 되겠다. 어디든 끼워넣을 수 있는 "[2631] 줄세우기" 문제와 연계하여 곱씹어볼만한 문제다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 1..
-
[9237] 이장님 초대BOJ 2021. 12. 25. 00:06
https://www.acmicpc.net/problem/9237 9237번: 이장님 초대 입력은 두 줄로 이루어져 있다. 첫째 줄에는 묘목의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄에는 각 나무가 다 자라는데 며칠이 걸리는지를 나타낸 ti가 주어진다. (1 ≤ ti ≤ 1,000,000) www.acmicpc.net 내림차순 정렬하여, 오래걸리는 묘목부터 처음에 심는다. 이후에는 v[i]+i의 최대값을 찾아 출력하면 되겠다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 #include using namespace std; int n, ans; vector v; int main(void) { cin >> n; v.resize(n); int i; for (i = 0; i ..
-
[15904] UCPC는 무엇의 약자일까?BOJ 2021. 12. 24. 23:38
https://www.acmicpc.net/problem/15904 15904번: UCPC는 무엇의 약자일까? 첫 번째 줄에 알파벳 대소문자, 공백으로 구성된 문자열이 주어진다. 문자열의 길이는 최대 1,000자이다. 문자열의 맨 앞과 맨 끝에 공백이 있는 경우는 없고, 공백이 연속해서 2번 이상 주어지는 www.acmicpc.net 앞부터 읽어가며, UCPC중 현재 등장해야 하는 문자가 등장하면, 그 횟수를 카운팅해준다. string base="UCPC"; 에 별도의 인덱스를 하나를 더 두어서 구현해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 #include using namespace std; string s, base = "UCPC"; int idx; int main(void) { ge..
-
[10610] 30BOJ 2021. 12. 24. 14:41
https://www.acmicpc.net/problem/10610 10610번: 30 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한 www.acmicpc.net 입력된걸 내림차순 정렬하고, 맨 뒤가 0이면서 총 합이 3으로 나누어 떨어지면 30의 배수이다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 #include using namespace std; string s; int sum; int main(void) { cin >> s; sort(s.begin(), s.end(), greater()); int i, S = s.length()..