Coding Feature.

Problem 16938번: 캠프 준비 난이도가 10, 30인 문제를 고르거나, 20, 30인 문제를 고르면 된다. www.acmicpc.net Solution. 정렬 알고리즘과 백트레킹 중 DFS 를 통해 풀이했다. 먼저 오름차순으로 문제의 난이도를 정렬해놓고 풀면 훨씬 좋을 것 같다는 판단 하에 버블 정렬을 이용했다. 그리고 이 문제는 조합으로 풀 수 있을 것 같아 DFS 알고리즘을 사용했다. DFS 를 하면서 다음과 같은 세 가지 조건이 만족하는 경우 count 를 1씩 늘려가며 답을 구했다. 1) 조합으로 만들어진 원소들의 합이 L보다 크거나 같다. (total >= L) 2) 조합으로 만들어진 원소들의 합이 R보다 작거나 같다. (total = X) 이때 3번 조건은 이미 오름차순으로 정렬된 수..

Problem. 16936번: 나3곱2 나3곱2 게임은 정수 하나를 이용한다. 가장 먼저, 정수 x로 시작하고, 연산을 N-1번 적용한다. 적용할 수 있는 연산은 두 가지 있고, 아래와 같다. 나3: x를 3으로 나눈다. x는 3으로 나누어 떨어져야 www.acmicpc.net Solution. 이 문제에는 두 가지 놓치거나 간과하기 쉬운 포인트들이 있다. 1) 수열 B에 포함된 각 숫자는 10^18 보다 같거나 작은 자연수이다. 즉 int 형이 아니라 long long 형(64bit)을 써야 한다는 것. 2) "가능한 정답이 여러가지인 경우에는 아무거나 출력한다." 라고 써져 있지만 사실은 정답은 하나밖에 없다. 나3곱2 연산으로 만들어지는 수열에는 순환이 생기지 않기 때문. (예. 2->4->8->2..

Problem 16924번: 십자가 찾기 십자가는 가운데에 '*'가 있고, 상하좌우 방향으로 모두 같은 길이의 '*'가 있는 모양이다. 십자가의 크기는 가운데를 중심으로 상하좌우 방향으로 있는 '*'의 개수이다. 십자가의 크기는 1보다 크 www.acmicpc.net Solution. 먼저 in_arr에 '*'인 경우 1, 나머지는 0으로 2차원 배열을 만든다. 그리고 행, 열의 각 index를 1에서부터 N-2, M-2 까지 탐색하며 (for문의 i, j 이용) in_arr[i][j] 가 1인 경우,(즉 십자가의 중심일 가능성이 있다. 아니면 그냥 별이덩가) k를 1로 초기화 시키고(k는 십자가의 크기를 의미) 난 뒤에 1씩 증가시키면서 k 범위 내의 십자가가 만들어지는지 확인했다. (행의 i-k, i..

Problem 16922번: 로마 숫자 만들기 2, 6, 10, 11, 15, 20, 51, 55, 60, 100을 만들 수 있다. www.acmicpc.net Solution. 백트레킹 기법 중 DFS 알고리즘을 사용해서 풀 수 있었다. 1, 5, 10, 50 총 4 가지 로마 숫자에 대해서 N개의 원소로 중복조합한 뒤 그 합을 구하면 된다. 중복 조합은 같은 걸 또 뽑으면서 조합할 수 있다는 뜻이다. 예를 들어 1 뽑고 또 1뽑고 해도 된다는 얘기. 이 문제에서 중복조합한 것의 합이 또 중복될 수 있는 게 관건이었다. 예를 들어 N이 6이라면 5, 10, 10, 10, 10, 10 = 55 1, 1, 1, 1, 1, 50 = 55 인 경우 둘 다 중복 조합 조건을 만족하지만 그 합은 중복이므로 이 둘..