매일 성장하자!!

문제 https://www.acmicpc.net/problem/3980 3980번: 선발 명단 각각의 테스트 케이스에 대해서, 모든 포지션의 선수를 채웠을 때, 능력치의 합의 최댓값을 한 줄에 하나씩 출력한다. 항상 하나 이상의 올바른 라인업을 만들 수 있다. www.acmicpc.net 풀이 11개의 포지션에 11명의 선수를 넣어주면 된다. 모든 경우의수를 돌며 최대 값을 뽑으면된다. 단, 해당 포지션의 성능이 0이면 해당 포지션에 선수를 배치하지 못하는 가지치기 조건을 이용해 경우의 수를 대폭 줄이면 된다. 즉, 백트래킹을 통해 가지치기로 시간적 이득을 봐야만 맞을수 있는 문제이다. 너무간단한데, 테스트 횟수가 있으므로 static 변수를 사용한다면 초기화를 계속 해줘야한다. (이거 놓쳐서 2번 틀림..

문제 https://www.acmicpc.net/problem/2661 2661번: 좋은수열 첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다. www.acmicpc.net 풀이 1 2 3 밖에 존재하지 못하는 수열중, 가장 작은 좋은 수열을 구하면 된다. 즉, 나쁜수열이면 안된다.. 가장 작은 숫자를 구하라 하였는데, 1 -> 2 -> 3 으로 탐색을 하면 자연스럽게 가장 작은 숫자가 나온다. 백트래킹 문제로 나쁜 수열이면 가지치기를 해서 경우를 많이 줄여 주면 간단하게 풀수있다. 즉, 재귀함수로 돌리다가 조건에 맞지않으면 그뒤의 가지들은 잘라버리고 다음 가지로 넘어간다...

문제 https://www.acmicpc.net/problem/1174 1174번: 줄어드는 숫자 음이 아닌 정수를 십진법으로 표기했을 때, 왼쪽에서부터 자리수가 감소할 때, 그 수를 줄어드는 숫자라고 한다. 예를 들어, 321와 950은 줄어드는 숫자이고, 322와 958은 아니다. N번째로 작은 줄어 www.acmicpc.net 풀이 문제는 너무 단순한데 보자마자 쉽게 어떻게 풀지 떠오르지가 않았습니다. 구래서, 일단 제일 작은수부터 나열해보았습니다. 0 1 2 0 1 2 3 4 5 6 7 8 9 10 20 21 30 31 32 40 41 42 43 50 51 52 53 54 60 61 62 63 64 65 70 71 72 73 74 75 76 80 81 82 83 84 ., 97 98 (세자리) 2..

문제 https://www.acmicpc.net/problem/16987 16987번: 계란으로 계란치기 원래 프로그래머의 기본 소양은 팔굽혀펴기를 단 한 개도 할 수 없는 것이라고 하지만 인범이는 3대 500을 넘기는 몇 안되는 프로그래머 중 한 명이다. 인범이는 BOJ에서 틀린 제출을 할 때마다 턱 www.acmicpc.net 풀이 백트래킹 문제이다. 적절하게 재귀함수를 이용해서 계란을 칠수있는 모든 경우의 수를 파악해야한다. 어떻게 하면 달걀을 집어서 칠 대상 달걀을 고르는 경우를 생각할수있을까? 일단 어떤식으로 할수있는지 간단하게 생각하자. 달걀 a, b, c, d, e 다섯개가 있다고하자. a 를 들고 b를 칠수있다. 그다음은 한칸 오른쪽 달걀을 들어야한다. 치는 대상은 아무거나 하나를 칠수있으..

문제 https://www.acmicpc.net/problem/10971 10971번: 외판원 순회 2 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 10) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net 풀이 백트래킹 문제이다. 재귀함수를 통해서 탐색하되, 가지치기를 통해 경우의 수를 줄여야한다. 재귀함수에대한 이해가 부족하면 풀기어렵다.(백트래킹 기본 N, M문제를 많이 풀어봐야한다 생각함!!) 2차원 배열로 어떠한 도시에서 어떠한 도시로가는 비용이 적혀있다. 외판원이 어떠한 도시에서 출발하여 모든 도시를 돌고 다시 시작한 어떠한 도시로 돌아오는..

문제 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으로 이동할 수 있는데, 새로 이동한 칸에 적혀 있는 알파벳은 지금까지 지나온 모든 칸에 적혀 있는 알파벳과는 달라야 한다. 즉, 같은 알파벳이 적힌 칸을 두 번 지날 수 없다. 좌측 상단에서 시작해서, 말이 최대한 몇 칸을 지날 수 있는지를 구하는 프로그램을 작성하시오. 말이 지나는 칸은 좌측 상단의 칸도 포함된다. 풀이 무지성으로 bfs로 했다. 문제를 자세히 살피지못하고.. 이문제는 무조건 깊이우선탐색 dfs로 풀어야한다.!!! 왜 그런지 알아보자. 같은 알파벳을 두번 지날수가없다. 즉, 한번 ..