어렵지는 않은 문제이다. 풀이방법은 다음과 같다. 1. Compare array에서 1을 가장 최우선적으로 체크한다. (1은 바로 0으로 만들면 연산을 아얘 안할 수 있개 때문이다.) 2. 0과 1이 아닌 원소를 고려하되, 짝수 홀수를 판단하여 홀수면 1개 줄이고 2로 나눠준다. (홀수라는 것은 해당 단계에서 +1을 해줬다는 의미이다. 왜냐하면 만약 그렇지 않다면 x2되어 짝수가 나오게 된다.) 위의 내용을 보면 그리디 알고리즘이라는 것을 인식해야 한다. 부분적으로 1. 1을 찾는다. 2. 0과 1이 아닌 수 중에 홀수면 -1시키고, 짝수면 그대로 납둔 상태에서 1/2시킨다. 3. 변경된 숫자들을 가지고 1, 2 과정을 반복한다. 즉, 초기 compare array에서 최적해를 다시 1, 2 과정으로 다..

일단 풀이방법을 다음과 같이 잡았다. 1.포션은 최대 체력의 절반 이하일때 섭취 (이때, 포션은 최대 절반만큼만 회복가능하므로 최대 HP를 넘어감으로써 손실량은 존재하지 않음) 2.위의 1번 결과에 의하여, 이길 방법이 존재하지 않는 경우는 초기 HP와 포션에 의한 총 회복량의 합이 싸움으로 인해 감소되는 HP보다 작을 때 발생 3.플레이어가 남을 때까지, 해당 플레이어의 공격을 빼고 절반 이하의 HP가 남을 경우 포션을 먹는 행위 반복(만약 포션이 없는 경우는 그대로 진행) 제일 중요한 접근 방법은 최대 절반을 기준으로 현재 HP의 Status를 판단하는 것이다. 포션을 절반보다 더 떨어졌을 때만 섭취하게 되면 Max_hp를 넘어갈 일이 존재하지 않으므로, 초반에 포션에 의한 HP증가량과 싸움에 의한 ..

상당히 교훈적인 문제이다. 이 문제는 입력 숫자가 작은 편이므로 Bruteforce 방법을 먼저 생각하는 것이 압도적으로 유리하다. 다만, 이 문제를 풀 때 가장 애를 먹은 사항이 중복되지 않으면서 채워나가는 것이다. 앞의 6.2장 피크닉 문제에서의 교훈인 "중복을 피하기 위해서 가장 좋은 방법이 가장 왼쪽 상단 index를 기준으로 하는 것이다"을 활용하여 조금씩 채워나가면 된다. 기본적인 문제 풀이의 방향성은 다음과 같다. 1. 비어있는 가장 왼쪽 상단 cordinate를 찾는다. 2. 해당 cordinate를 덮을 수 있는 블록을 찾는다.(이 과정에서 블록이 외부로 넘어가는지 여부를 체크한다.) 3. 해당 블록을 덮었다고 가정하고 이후의 과정을 반복한다. (재귀를 활용해서 이를 구현하되, 각 단계가..

문제 자체는 어렵지 않은 편이다. 친구인 학생들끼리만 짝을 지어주어야 하므로 입력받은 짝을 순차적으로 Brute-force방법을 활용하여 탐색해주면 된다. #include #include #include using namespace std; int student_num, friend_pair_num; int result = 0; void group_maker(vector &friend_store, vector &pair_store, int check_num, int index){ // 확인하는 케이스(총 member수가 구해야하는 것과 같을 때 전체 케이스를 만족하는지 체크) if(check_num == 0){ vector check_value(student_num, 0); for(int i = 0; i..

실수를 상당히 많이 해서 시간이 오래 걸렸다.. 제일 중요한 것은 index 실수를 하였다. 처음에 풀 때 돌아가는 톱니바퀴를 따로 저장해두고 한번에 돌리는 아이디어를 짠 것 까지는 좋은데, 들어가는 index와 매칭시키는 것을 실수하였다. 해당 문제점때문에 매칭이 잘못되어 틀리게 나왔었다. 또한 추가적으로 생각해보면, 각 상태를 따로 저장해두지 말고 이중배열로 data를 저장해두었으면 if문을 상당히 줄일 수 있었다. first, second, third, fourth를 나누어서 vector에 정보를 저장해두었는데 생각해보니까 매우 비효율적인 것 같다. 사실 그러한 방향성만 수정하였으면 코드 자체는 그리 길지 않게 해결할 수 있을 것 같다. (다시 짤까 고민도 했었는데.. 귀찮아서 포기.. ) 대략적으..

숫자를 크게 보면, S + 1을 기준으로 나머지가 0인 3개의 부분과, 나머지가 1이 아닌 2개의 부분으로 구획 가능하다. 이것을 기준으로 or 연산자를 활용해서 쉽게 계산할 수는 있다. (다만, 귀찮아서 그냥 0~9까지 케이스를 각각 저장해두고 필요할때마다 꺼내 쓰는 방식을 채택하였다.) 매우 비효율적인 코드이지만 그냥 넘어가자.(귀찮다.) #include #include #include #include #include using namespace std; int main(void){ int S; string N; cin >> S >> N; char zero_store[23][12]; char one_store[23][12]; char two_store[23][12]; char three_store[2..

사실.. 처음 풀 때 순간적으로 착각하여 오래 풀게 되었다. 단순히 옮기는 것이므로, 각 component에 해당하는 숫자가 그대로 노출되어 있는 부분이 반드시 존재할 것으로 착각하였으나 그렇지 않은 부분도 있었다. 대표적인 예시가 3 4 1 1 1 2 3 4 0 5 7 9 11 4 9 15 17 19 8 0 9 10 11 12 이다. 이 경우에는 6, 7 부분이 직접적으로 나오지는 않는다. 따라서 풀이방법은 다음과 같다. 1. 덧셈이 아니라 직접적으로 노출된 부분을 store한다. (단, 해당 배열의 default 상태를 -1로 두어 저장된 것인지 아닌지를 구분한다.) 2. 겹치는 부분을 기준으로 찾되, 더해진 2개의 index값 중 default 상태에서 변화된 부분이 있으면 그것을 통해 나머지 in..

처음에 이 문제를 보고 자연스럽게 생각나는 풀이방법은 이중 for loop를 활용하여 계속해서 해당 결과값들을 더해나가는 것이다. 그런데, 그런 방식으로 풀게 될 경우 데이터가 10만개이므로 시간 복잡도가 대략 O(n^3)가 나온다. (시그마 계산을 하게 되면 이는 쉽게 증명할 수 있다.) 그러면 최악의 경우를 고민해보았을 때 시간초과가 난다는 사실을 알 수 있다. 그렇기에 다른 방법을 강구해야 한다. 잘 생각해보면 결과적으로 하나의 숫자는 다른 모든 숫자와 곱해지는 형태이므로 전체 sum에서 자기 자신을 뺀 만큼이 곱해지게 되는 양상으로 진행되게 된다.(결합법칙 정도로 이해하면 충분하다.) 다만, 중복되는 것을 감안해서 마지막에 1/2처리만 해주면 된다. 일종의 대각선 갯수 구하는 알고리즘이랑 느낌이 ..