개발 블로그

https://www.acmicpc.net/problem/9019 9019번: DSLR 네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 www.acmicpc.net 이 문제는 BFS라고 볼 수 있습니다. 시작 값과 끝 값을 두고 D(num*2 % 10000), S( s-1 > 0 ? 9999 : s-1), L(자리수 왼쪽 한 칸 이동), R(자리 수 오른쪽으로 한 칸 이동) 연산을 하는데, 시작 값에서 끝 값을 만들기 위한 연산의 최솟값을 구하는 문제입니다. 3 1234 3412 1000 1 1 16 테스트케이스를 예시로 들면, 1234에서 34..

https://www.acmicpc.net/problem/16928 16928번: 뱀과 사다리 게임 첫째 줄에 게임판에 있는 사다리의 수 N(1 ≤ N ≤ 15)과 뱀의 수 M(1 ≤ M ≤ 15)이 주어진다. 둘째 줄부터 N개의 줄에는 사다리의 정보를 의미하는 x, y (x < y)가 주어진다. x번 칸에 도착하면, y번 칸으 www.acmicpc.net 이 문제는 뱀과 사다리에 대한 정보가 주어지고, 사다리는 해당 칸에서 위로 올라갈 수 있지만, 뱀은 아래로 내려가는 구조입니다. 만약 사다리나 뱀을 만나지 않는다면, 주사위를 던져 나올 수 있는 모든 경로를 탐색하면 됩니다(6가지) #include #include using namespace std; int dist[101]; int nex[101];..

https://www.acmicpc.net/problem/16197 16197번: 두 동전 N×M 크기의 보드와 4개의 버튼으로 이루어진 게임이 있다. 보드는 1×1크기의 정사각형 칸으로 나누어져 있고, 각각의 칸은 비어있거나, 벽이다. 두 개의 빈 칸에는 동전이 하나씩 놓여져 있고, www.acmicpc.net 이 문제는 동전을 하나만 떨어뜨리기 위한 최솟값을 구하는 문제입니다. 만약 횟수가 10번 넘기거나, 동전이 둘 다 떨어지는 경우는 -1을 출력해야 합니다. 코드로 설명드리겠습니다. #include #include using namespace std; int n, m; string a[20]; int mov[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; int go..

https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 이 문제는 주어진 배열의 해당하는 값 4개를 더한 값들 중 최댓값을 구해야 하는 문제입니다. 그렇지만, 예외처리 해줘야 하는 부분이 있습니다. ㅗ,ㅜ,ㅏ,ㅓ와 같은 테트로미노 모양은 DFS탐색이 불가능 합니다. 그래서 따로 함수를 만들어서 처리해줘야 하는 번거로움이 있습니다. 그 외에는 백트래킹으로 접근해서 테트로미노의 칸에 놓은 수들의 합의 최댓값을 구해주면 됩니다. 더불어, 이 문제는 DFS ..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 로또의 당첨 번호는 6개입니다. 입력받은 숫자들 중 6개의 순서쌍을 오름차순으로 모든 경우의 수를 출력해 주는 문제입니다. 백트래킹으로 접근할 수 있습니다. 만약 해당 인덱스의 숫자를 사용한다면 함수는 다음과 같이 정의 할 수 있습니다. solve(a, index+1, cnt+1) 해당 인덱스의 숫자를 사용하지 않는다면, 개수는 늘려주지 않고, 해당 인덱스만 1 늘려주면 끝입니다. so..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 이 문제는 풀 수 있는 방법이 매우 많습니다. 백트래킹도 가능하고, 순열로도 풀 수 있습니다. 저는 순열로 풀었는데 C++에 next_permutaion 내장 함수를 이용하면 구현 방식이 간단하고, 무엇보다 가독성이 좋기 때문입니다. 그리고 모든 연산자의 최대 개수가 10! / (3! * 3! * 2! * 2!) = 2520가지입니다. 이러한..

https://www.acmicpc.net/problem/1495 1495번: 기타리스트 첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다. www.acmicpc.net 문제에서 주어지는 입력은 N(연주할 곡), S(시작 볼륨), M(최대 볼륨)입니다. 두 번째 입력에서는 연주할 곡의 볼륨입니다. 연주는 P-V[i], P+V[i]의 볼륨으로만 연주해야 하고, 구하고자 하는 결과는 마지막 곡을 연주했을 때의 볼륨의 최댓값입니다. D[i][j]는 i번 곡을 j로 연주할 수 있으면 true, 그렇지 않으면 false를 반환합니다. ..

https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 주어진 입력은 배낭의 무게(w)와 가치(v)입니다. 배낭의 수용량을 넘지 않으면서 가치의 최댓값을 구하는 문제입니다. 점화식은 다음과 같이 세울 수 있습니다. 물건을 담지 않은 경우 D[i][j] = D[i-1][j] 물건을 담은 경우 D[i][j] = D[i-1][j-w[i]] + v[i] 물건을 담은 경우 에는 수용량과 가치 갱..

https://www.acmicpc.net/problem/11066 11066번: 파일 합치기 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본 www.acmicpc.net 이 문제는 파일을 합치는데 최소 비용을 구하는 문제입니다. 테스트케이스를 예시로 들면, C1, C2, C3, C4의 파일 크기는 각각 40 30 30 50입니다. 파일을 합치는 경우의 수는 총 3가지입니다. (C1), (C2, C3, C4) (C1, C2), (C3, C4) (C1, C2, C3), (C4) 1번 경우에는 C2 + C3 = 60, C2 + C3 + C4 = 60 + 50 ..

https://www.acmicpc.net/problem/10942 10942번: 팰린드롬? 총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다. www.acmicpc.net 이 문제는 기존 팰린드롬(Palindrome)과 유사한 문제입니다. 주어진 수열이 있는데, 시작 인덱스, 끝 인덱스를 입력받고 이 수열이 팰린드롬이면 1을 출력, 그렇지 않으면 0을 출력하는 문제입니다. 팰린드롬은 길이가 1이면 무조건 팰린드롬이고, 2이면 하나만 비교해 주면 됩니다. 이제, 길이가 3인 경우에는 i(첫번째 인덱스), j(마지막 인덱스)에서 인덱스를 하나씩 늘리고(시작 인덱스), 줄여나가면서(마지막 인덱스) 배열 값이 ..