N으로 표현 입출력 예 N : 5 number : 12 return : 4 해결 방법 제가 푼 방법은 N 2개 가지고 가능한 모든 수를 구하고 n이 3개를 이용한 값을 만들기 위해서 n이 2개 사용한 값과 n이 하나인 모든 값을 n이 3개인 값의 배열에 저장합니다(1개 X 2개 , 2개 X 1개) n이 4개를 이용한 값을 만들기 위해서 1개X3개 2개X2개 3개X1개 배열들의 모든 값들을 n이 4개인 배열에 저장합니다. 이런 방법으로 문제를 풀면 정답이 나왔습니다. 당연히 n이 많을 수록 나오는 값이 굉장히 불어납니다. 그래서 효율은 많이 떨어지는 코드입니다. 소스 코드 #include #include #include using namespace std; int func1(int number) { int..
셔틀버스 입출력 예제 n = 1;t = 1;m = 5;timetable = { "08:00", "08:01", "08:02", "08:03" };return : "09:00" 해결 방법 이 문제는 콘이라는 사람이 막차를 타고 가장 늦게 타는 것이 핵심입니다.처음에 timetable의 시간은 제각각이라서 우선순위 큐를 이용해서 정렬해줬습니다.막차가 아니면 그 시간대의 사람은 전부 태울 수 있고 막차가 아닌데 그 시간대에 탈 수 있는 사람이 없다면 태울 수 있는 사람만 태우고 가버리면 되고 막차이든 막차가 아니든 사람이 없으면 가장 마지막 배차를 반환해 줘야 합니다. 그리고 막차인데 태울 수 있는 한도가 많을 경우 가장 마지막번째의 타는 사람보다 1분 도착하도록 반환을 해주는 것으로 풀었습니다. 정말 무식하..
추석 트래픽 입출력 예제 lines: [ 2016-09-15 20:59:57.421 0.351s, 2016-09-15 20:59:58.233 1.181s, 2016-09-15 20:59:58.299 0.8s, 2016-09-15 20:59:58.688 1.041s, 2016-09-15 20:59:59.591 1.412s, 2016-09-15 21:00:00.464 1.466s, 2016-09-15 21:00:00.741 1.581s, 2016-09-15 21:00:00.748 2.31s, 2016-09-15 21:00:00.966 0.381s, 2016-09-15 21:00:02.066 2.62s ] return : 7 문제 해결 수많은 에러때문에 무식하게 풀어버렸네요. 2016년 9월 15일 필요없고 ..
뉴스 클러스터링 입출력 예제 str1 : FRANCEstr2 : french 해결 방법 문제에서 2개의 문자 만들어야한다. 조합으로 만드는것이 아니라 순서대로 2글자 만드는 것이므로 for문 1개로 해당 위치와 다음 위치를 불러와서 저는 multiset에 저장했습니다. 2개의 집합을 만들어 냈으면 1번째 집합의 개수만큼 union을 더하고 2번째 집합에 대해서 1번째의 값이 속해있으면 intersaction에 더하고 없으면 union에 더하면서 풀어나가면 해결이 된다. 만약 속한게 있으면 1번째 집합에 있는 해당 값을 없애 줘야 한다. 소스 코드 #include #include #include #include using namespace std; int solution(string str1, string..
프렌즈4블록 입풀력 예제 m=4 n=5board : ["CCBDE","AAADE","AAABF","CCBBF"]answer : 14 풀이과정mXn 길이를 처음에 4블록인 것을 확인하기 위해서 높이는 m-1까지 , 폭은 n-1까지 확인해서 해당 위치에 오른쪽 아래쪽, 대각선 위치랑 같은 지 확인을 해서 전부 같으면 블록을 내리면 된다. 4블록이 완성이 되면 visit[n][m] 확인 배열을 이용해서 체크해둔다.그리고 제거할때마다 visit가 true이면 answer를 증가시키고 위에서 한칸씩 내리는 방법을 이용했다.내릴 때 1칸씩 내리기 때문에 효율은 굉장히 나쁘지만 구현할 때 매우 편하다. 그리고 내리면서 빈 공간은 0으로 저장시키면서 board가 0일때는 그냥 무시하게 만들어야 했다. 소스코드 #inc..
다트 게임 입출력 예제 dartResult : 1S2D*3Tanswer : 37 풀이 과정저는 이 문제를 문제 과정 그대로 따라가듯이 했습니다 숫자를 읽어 들이고 그다음 문자를 읽고 스타상일 때 과정, 아차상일 때 과정 둘다 존재하지 않을 때 과정을 따로 if문을 이용해서 문제를 해결해나갔습니다.c++에서 string에서 int로 바꾸는 방법은 stoi()함수를 이용해서 정수형으로 사용할 수 있습니다.그리고 flag를 이용해서 첫번째 스타상일 때 처리를 하려고 만들었습니다. 이것때문에 다른 아차상과 보너스가 없을 때도 flag를 처리해야 해서 코드가 길어져버렸네요. 너무 많아서 flag를 내려도 되겠지만 처음 구현했을 때여서 수정을 하지 않았습니다.각 숫자마다 계산이 되면 vnumber라는 배열에 저장을..
캐시 입출력 예제cacheSize : 3 cities : [ "Jeju","Pangyo","Seoul","NewYork","LA","Jeju","Pangyo","Seoul","NewYork","LA" ]return : 50 풀이과정문제에서의 조건은 LRU입니다. 최근에 사용된 것을 교체시켜야 합니다 일단 cacheSize만큼 공간을 만들기 위해 배열로 만들고 캐쉬의 사용 순서를 알기 위한 배열을 또 만들었습니다.그다음 cities를 한개씩 풀러오면서 캐시에 내용이 존재하지 않으면 값을 집어넣고 사용 순서는 count라는 숫자로 그냥 1개씩 늘렸습니다.count가 높을 수록 최근에 사용된 캐시라는 것으로 이용해서 캐시 사이즈가 꽉찼을 경우 count가 가장 큰 것을 바꾸는 방법을 이용해서 값을 구했습니다...
비밀지도 입출력 예제n : 5arr1 : [9,20,28,18,11]arr2 : [30,1,21,17,28]return : ["#####","# # #","### #","# ##",'#####"] 문제해설이번 문제를 풀려면 비트연산인 | 연산을 이용하면 바로 내가 원하는 값이 나오고 그것을 2진수로 바꾸는 과정을 이용해서 해결할 수 있습니다. 저는 string에 5개의 공간을 공백으로 만들고 2로 나누면서 나머지가 존재하면 뒤에서부터 #을 채우는 방식으로 2진수로 만들었습니다. 소스코드#include #include using namespace std; vector solution(int n, vector arr1, vector arr2) { vector answer(n); for (int i = 0; ..
문제 설명도둑이 어느 마을을 털 계획을 하고 있습니다. 이 마을의 모든 집들은 아래 그림과 같이 동그랗게 배치되어 있습니다.각 집들은 서로 인접한 집들과 방범장치가 연결되어 있기 때문에 인접한 두 집을 털면 경보가 울립니다.각 집에 있는 돈이 담긴 배열 money가 주어질 때, 도둑이 훔칠 수 있는 돈의 최댓값을 return 하도록 solution 함수를 작성하세요. 해결 방법동그랗게 배치되어 있기 때문에 배열의 첫번째 집이 만약 훔친다면 마지막 집은 훔칠수 없습니다. 그리고 첫번째 값이 훔치지 않았다면 마지막 집을 훔칠 수 있습니다.이 2가지 경우를 고려하면서 문제를 풀어나갔습니다.인접한 집이 아닐 경우는 자신의 위치에서 1칸 띄거나 2칸 띌 수 있습니다. 이를 이용해서 동적계획으로 N번째의 집까지 훔..
문제 설명 국가의 역할 중 하나는 여러 지방의 예산요청을 심사하여 국가의 예산을 분배하는 것입니다. 국가예산의 총액은 미리 정해져 있어서 모든 예산요청을 배정해 주기는 어려울 수도 있습니다. 그래서 정해진 총액 이하에서 가능한 한 최대의 총 예산을 다음과 같은 방법으로 배정합니다. 1. 모든 요청이 배정될 수 있는 경우에는 요청한 금액을 그대로 배정합니다.2. 모든 요청이 배정될 수 없는 경우에는 특정한 정수 상한액을 계산하여 그 이상인 예산요청에는 모두 상한액을 배정합니다. 상한액 이하의 예산요청에 대해서는 요청한 금액을 그대로 배정합니다. 예를 들어, 전체 국가예산이 485이고 4개 지방의 예산요청이 각각 120, 110, 140, 150일 때, 상한액을 127로 잡으면 위의 요청들에 대해서 각각 1..