그리디 알고리즘3 [BOJ] 1041번 - 주사위 밑면을 제외한 나머지 5면의 숫자들의 합을 최솟값으로 출력하는 문제이다. 이 문제를 쉽게 해결하기 위해선 주사위마다 몇개의 면이 보이는지를 분류해야 하는데 위 그림을 보는 것처럼 5면은 1개의 윗면과 4개의 옆면으로 이루어져 있다. 빨간색 : 3면이 보이는 주사위 파란색 : 2면이 보이는 주사위 초록색 : 1면이 보이는 주사위 이를 수식화하여 표현하면 한변의 길이가 N인 정육면체의 주사위인 경우 다음과 같이 나타낼 수있다. 3면이 보이는 주사위 : 4 2면이 보이는 주사위 : 4*(N-1) + 4*(N-2) 1면이 보이는 주사위 : 4*(N-1)*(N-2) + (N-2)*(N-2) 그리고 이 세개의 면에 보이는 숫자들은 6개의 주사위의 숫자중에 마주보는 숫자끼리 중 작은것들로 채우면 된다. #includ.. 2022. 6. 16. [BOJ] 16953번 - A → B 문제에서는 A를 B로 바꾼다고 했지만 B에서 A로 바꾸는게 코드 짜기 훨씬 편하다. 조건을 나눠본다면 먼저 짝수냐 홀수이냐를 크게 구분할 수 있는데 여기서 문제 조건인 1을 수의 가장 오른쪽에 추가한다는 내용 때문에 1. 가장 먼저 if문에 1의자리가 1인지 확인한다. 10으로 나누고 count ++, 반복문 진행 2. 다음으로 홀수인지 확인 조건에 있는 연산으로는 1을 제외한 홀수의 숫자가 나올 수 없기 때문에 -1 출력하고 종료 3. 그 외의 나머지 경우 2로 나누고 count ++, 반복문 진행 4. while문 내의 조건을 만족하고 빠져나온 경우 주어진 조건인 2를 곱하거나 1을 수의 가장 오른쪽에 추가하는 것으로 숫자를 변환 할수 없으므로 -1 출력하고 종료 #include using names.. 2022. 6. 16. [BOJ] 1339번 - 단어 수학 알파벳으로 이루어진 문자열을 각각 자릿수마다 숫자로 바꾸어 합의 최대값을 구하는 문제이다. 문제의 예시를 살펴보면 GCF와 ACDEB의 합의 최대값을 구하는 경우를 보면 A*10000 + C*1000 + (D+G)*100 + (E+C)*100 + (B+F)로 표현할 수 있다. 이때 빈도수가 가장 많은 순서대로 알파벳에 값을 넣어주면 되므로 A : 9 / C : 8 / D : 7 / G : 6 / E : 5 / B : 4 / F : 3으로 대입하고 최대값을 계산하면 99437이 나온다. 단계 1 : char로 이루어진 문자열 형태를 알파벳 별 개수로 변환하여 배열에 넣는다. 단계 2 : 알파벳 별 개수를 sort해준다 - 빈도수가 많은 것부터 큰 수를 넣어주기 위해 단계 3 : 9부터 대입하여 알맞은 숫자.. 2022. 6. 15. 이전 1 다음
