https://www.acmicpc.net/problem/15655 15655번: N과 M (6) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이 문제는 15654번과 15650번을 합친 문제라고 생각할 수 있다. 풀이는 간단하다. 입력 받은 배열을 이용하여 dfs를 구현하는 것이다. 중요한 것은 중복이 없고 앞자리 수보다 작은 수는 오지 않게 만든다는 것이다. 그럼으로 15650번과 마찬가지로 at 변수를 사용하여 시작지점을 설정하여 출력하면 된다. 15650번과 같은 방식과 15654의 배열 이용 방법을 이용한 것이기 때문에..
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 이번 문제는 저번 스타트링크 문제를 풀고 백트래킹을 더 공부해야겠다고 생각해서 N과 M을 전부 풀어볼 목적으로 한다. 이 문제는 저번 15649번의 코드를 아주 조금 바꾸면 되기에 간단하게 설명하겠다. 먼저 각 수열 내부의 중복을 제거해야하지만, 각 수열로 봤을 때 역순은 있어야한다. 그렇기에 방문체크를 사용하여 이 문제를 해결 할 것이다. 출력은 다른 N과 M문제들과 마찬가지로 깊이가 ..
https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 이번 문제는 많은 감자짓을 통해 해결한 문제이다. 알고리즘 장인 선배의 도움이 없었다면 못풀고 몇일을 고민하다 답지 봤겠지.. 처음 이 문제를 봤을 때 문제의 이해를 조금 잘못해서 삽질의 시간이 좀 더 오래걸렸다. 나는 팀을 주어진 수에서 2명씩 골라서 2팀을 만드는 문제인줄 알고 삽질하다가 선배가 문제 설명해줘서 이해하고 접근을 시작했다. 그런데도 접근 방법이 떠오르지 않아서 도움을 통해 접근했다...ㅎㅎ 그래서 이..
https://www.acmicpc.net/problem/15650 15650번: N과 M (2) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15651 15651번: N과 M (3) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net https://www.acmicpc.net/problem/15652 15652번: ..
https://www.acmicpc.net/problem/15649 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 이 문제는 처음하는 DFS문제여서 너무 어려웠다.... 그래서 결국 다른 사람의 해설을 봤다. DFS와 BFS문제를 여러개 풀어봐야겠다. 원리는 이렇다. 먼저 Int형 배열에 탐색 깊이를 기준으로 index값을 집어 넣는 것이다. 예를 들어보면, N=4, M=2라고 했을 때 N은 요소의 범위이고 M은 깊이이다. 1부터 4에서 1을 골랐을 때 깊이가 2인 수열은 1 2, 1 3, 1 4이다. 즉,..
https://www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 이 문제를 풀면서 내가 수학과 규칙성 찾기가 많이 부족하구나를 느꼈다... 처음에 이 문제를 시도했을 때는 단순 하드 코딩 밖에 생각나지 않았다.. 그래서 바로 메모리 초과로 뚜드려 맞고 고민을 해보았다. 그런데 도저히 방도가 생각나지 않았다. 그래서 이제 미지수를 두어서 여러가지 시도를 해보았다. 미지수를 두고 방정식을 세워서 더해도 보고, 빼보기도 하면서 무언가 감이 올듯 오지 않아서 결국 또 질문 게시판을 ..
https://www.acmicpc.net/problem/1002 1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다. www.acmicpc.net 이 문제는 경우를 따지는 것이 조금 어려웠다. 처음에는 접근 방법을 어떤 식으로 해야하나 고민하면서 그림을 여러 차례 그려보면서 조금씩 이해했고, 반례를 찾기위해 저번처럼 질문 게시판의 반례들을 사용해보면서 경우를 찾아 냈다. 원리는 정리해보면 간단하다. 두 좌표지점에서 그리는 각각의 원이 접해서 생기는 점의 갯수를 구하는 것이다. 경우는 접하지 않는 경우, 접하는 경우, 원 안에 원이 포함되어 접하는 경우, 원 안에 원이 포함된 경우, 원이 같은 ..
https://www.acmicpc.net/problem/2477 2477번: 참외밭 첫 번째 줄에 1m2의 넓이에 자라는 참외의 개수를 나타내는 양의 정수 K (1 ≤ K ≤ 20)가 주어진다. 참외밭을 나타내는 육각형의 임의의 한 꼭짓점에서 출발하여 반시계방향으로 둘레를 돌면서 지 www.acmicpc.net 이번 문제는 참외밭이다. 문제를 이해하면서 조금 어려움이 있었다. 처음에는 그냥 전체 넓이에서 짤린 부분을 계산하면 되겠지라고 생각해서 하는데 이게 주어지는 입력이 반시계방향 순서대로 주어지는게 맞는지 반례들을 보다보니 헷갈렸다. 그래서 도저히 모르겠어서 다른 사람들의 코드를 보면서 이해를 했다... 내가 맨 처음 생각한 원리와 비슷하지만 조금 다른 풀이 방법이다. 일단 제일 긴 가로와 세로를 ..
