이모저모

https://www.acmicpc.net/problem/11048 11048번: 이동하기 준규는 N×M 크기의 미로에 갇혀있다. 미로는 1×1크기의 방으로 나누어져 있고, 각 방에는 사탕이 놓여져 있다. 미로의 가장 왼쪽 윗 방은 (1, 1)이고, 가장 오른쪽 아랫 방은 (N, M)이다. 준규는 www.acmicpc.net 문제 해결 방법 처음 문제를 접했을 때, 단순한 완전탐색 문제라고 생각했습니다. 사탕의 최댓값을 구하기 위해 모든 칸을 탐색하여 진행하는 방식을 떠올렸습니다. 마침 이동하는 범위도 (0,1) (1,0) (1,1) 이기에 범위도 신경쓸 부분이 줄어들었다 생각했습니다. 처음 작성한 코드는 아래와 같습니다. import java.io.*; import java.util.*; public ..

https://www.acmicpc.net/problem/14225 14225번: 부분수열의 합 수열 S가 주어졌을 때, 수열 S의 부분 수열의 합으로 나올 수 없는 가장 작은 자연수를 구하는 프로그램을 작성하시오. 예를 들어, S = [5, 1, 2]인 경우에 1, 2, 3(=1+2), 5, 6(=1+5), 7(=2+5), 8(=1+2+5)을 만들 www.acmicpc.net 문제 해결 과정 예제 입력 1번 경우의 그림이다. 아무 것도 없는 상태에서 각 배열의 값을 DFS 방식으로 탐색하며 store라는 배열에 각 수열의 합을 채워 넣는 방식이다. 이때, store 배열은 조건에 "100,00보다 작거나 같은 수" 가 최대 20개까지 주어지니까 1~2,000,000 으로 범위를 생각하여 store의 배..

https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 문제 해결 방법 순열 문제라고 생각했습니다. 기본적으로 k개의 수 중 6개의 수를 골라야 하며, 수는 사전순으로(오름차순) 배치를 해야 하기에 범위를 나눠 생각했습니다. k개의 수 중 첫번째 자리에 올 수 있는 수는 (k-6)+1 가지 입니다. 예를 들어, k가 7이라면 첫번째로 올 수 있는 수는 1과 2 입니다. 3이 되는 순간 3, 4, 5, 6, 7 이 다섯 가지의 수밖에 없기 때..

https://www.acmicpc.net/problem/1913 1913번: 달팽이 N개의 줄에 걸쳐 표를 출력한다. 각 줄에 N개의 자연수를 한 칸씩 띄어서 출력하면 되며, 자릿수를 맞출 필요가 없다. N+1번째 줄에는 입력받은 자연수의 좌표를 나타내는 두 정수를 한 칸 띄어서 www.acmicpc.net 문제 접근 방법 달팽이가 움직이는 모습은 위와 같다. 시작점을 먼저 찾고 ( N/2, N/2 ) 시작점을 기준으로 움직일 수 있는 범위를 제한하여 구동하면 된다. 예를 들어 1->2, 2->3을 갈때는 최대 한 칸만 움직일 수 있지만 3->5, 7->10 등 움직일 수 있는 범위가 늘어나는 포인트가 생긴다. 이 포인트들은 달팽이가 위, 아래로 움직일 때 (x,y에서 x값이 증가하거나 감소할 때) 이..