BOJ
-
[18138] 리유나는 세일러복을 좋아해BOJ 2021. 12. 31. 18:03
https://www.acmicpc.net/problem/18138 18138번: 리유나는 세일러복을 좋아해 너비가 3인 티셔츠와 너비가 2인 세일러 카라를 붙이고, 너비가 5인 티셔츠에 너비가 5인 세일러 카라를 붙이고 너비가 7인 티셔츠에 너비가 4인 세일러 카라를 붙이고 너비가 10인 티셔츠에 너비 www.acmicpc.net 집합의 원소의 개수 n, m과 n개의 집합 x, m개의 집합 y가 주어진다. 티셔츠와 카라를 합쳐서 세일러복을 만들 수 있다면 두 정점간 간선을 생성해준다. 이후 이분매칭을 돌려주어 최대 매칭 수를 구하면 된다. 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..
-
[1071] 소트BOJ 2021. 12. 31. 08:18
https://www.acmicpc.net/problem/1071 1071번: 소트 N개의 정수가 주어지면, 이것을 연속된 두 수가 연속된 값이 아니게 정렬(A[i] + 1 ≠ A[i+1])하는 프로그램을 작성하시오. 가능한 것이 여러 가지라면 사전순으로 가장 앞서는 것을 출력한다. www.acmicpc.net 결론적으로 nlogn에 풀렸는데, n이 50으로 엄청 작아서 의아하다. 백트래킹으로 풀리는지는 잘 모르겠다... n이 이 문제보다 큰 100이어도 가지치기를 통해 백트래킹이 돌아갔던 문제가 하나 있는데, "[6590] 덧셈 체인" 처럼 백트래킹이 될 것이란 확신을 갖기 쉽지 않다. 이 문제는 두가지가 풀이를 구상하는 데에 꽤나 큰 힌트가 되었다. 첫번째는 "사전 순으로 가장 앞서는.."의 조건이고..
-
[12904] A와 BBOJ 2021. 12. 30. 02:28
https://www.acmicpc.net/problem/12904 12904번: A와 B 수빈이는 A와 B로만 이루어진 영어 단어가 존재한다는 사실에 놀랐다. 대표적인 예로 AB (Abdominal의 약자), BAA (양의 울음 소리), AA (용암의 종류), ABBA (스웨덴 팝 그룹)이 있다. 이런 사실에 놀란 수 www.acmicpc.net s->t는 어렵지만, t->s는 유일하다. t의 맨 뒤가 'A'인 경우와 'B'인 경우를 나누어, 문제에 설명된 연산을 반대로 구현하면 된다. t가 empty string이 되기 전에 s와 같아지면 s를 t로 만들 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 #include using name..
-
[2628] 종이자르기BOJ 2021. 12. 29. 04:46
https://www.acmicpc.net/problem/2628 2628번: 종이자르기 첫줄에는 종이의 가로와 세로의 길이가 차례로 자연수로 주어진다. 가로와 세로의 길이는 최대 100㎝이다. 둘째 줄에는 칼로 잘라야하는 점선의 개수가 주어진다. 셋째 줄부터 마지막 줄까지 한 www.acmicpc.net 선형 자료구조 2개를 만들어서, 각각 {0, n}과 {0, m}으로 초기화한다. 가로와 세로의 순서에 맞게 입력되는 점선 번호를 전부 넣어주고, 정렬한다. v[i+1]-v[i]의 최대값을 가로에서 한번, 세로에서 한번 찾아서 두 수를 곱해주면 된다. 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 #incl..
-
[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..