링크: https://www.acmicpc.net/problem/15657 15657번: N과 M (8) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 아이디어 백트래킹을 이용해 고르는 경우의 수를 찾자 m개가 골라졌을 때 고른 수를 print하고 return 백트래킹의 인자로 고른 수의 인덱스 번호를 넘겨주어 그 인덱스 번호부터 n번째 수 사이에서 또 선택하게 설계 위 논리를 적용하는 이유는 비 내림차순으로 하기 위함이니 입력받은 수를 오름차순 정렬해주어 백트래킹 시작 구현 import sys def back(inx): if l..
링크: https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net 아이디어 dp를 이용해서 풀면 될거라고 바로 보임 왼쪽의 스티커부터 선택해 나가 dp배열을 채워나가보자 예제에서 보자 왠쪽부터 dp 배열을 만들어 간다고 하면 첫줄은 50과 30이 그대로 들어간다. 이제 두번째 줄은 대각으로 더한 값이 가장 큰 코스트가 되는 경우니 둘을 더한 값을 dp에 저장한다. 이렇게 셋팅이 됐다면 점화식이 들어가면 된다. (0,2) 좌표의 스티커가 선택되는..
링크: https://www.acmicpc.net/problem/11729 11729번: 하노이 탑 이동 순서 세 개의 장대가 있고 첫 번째 장대에는 반경이 서로 다른 n개의 원판이 쌓여 있다. 각 원판은 반경이 큰 순서대로 쌓여있다. 이제 수도승들이 다음 규칙에 따라 첫 번째 장대에서 세 번째 장대로 www.acmicpc.net 풀이 이 문제는 3개의 장대에 각각 역할? 부여하고 생각해야했다. 첫 시작은 1번 장대는 start, 2번 장대는 sㅕpport, 3번 장대는 target으로 두자 start 장대에 원판이 n개가 있다고 가정하면 어쨌거나 n-1개의 원판을 support 장대로 옮기고 가장큰(맨아래) 원판을 target 장대로 이동시키면 이 원판은 고정이다. 이 상황을 다시 보면 1번 장대 ->..
링크: https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 아이디어 끝나는 회의 순서대로 정렬해야 가장 많은 회의의 수를 알 수 있을듯? 빨리 끝나면 더 많은 회의를 할 기회가 많기 때문에 ㅇㅇ 회의 시작 시간과 끝나는 시간이 같은 경우도 있기 때문에 회의 시작 시간을 2순위로 정렬을 해줘야함 2, 2와 1, 2가 있으면 1, 2를 먼저 하면 2,2도 활 수 있지만 2,2을 먼저 해버리면 1, 2는 무시되버린다. sort 키에 람다를 활용해 정렬 기준 1순위로 끝나는 시간 2순위로 시작시간으로 정렬을 해준다 이 후 정렬된 배열을 가지고 for문을 돌아 시작할 수 ..
링크: https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 처음 생각 길이를 기준으로 정렬 for문을 돌며 이웃한 요소의 길이차를 비교 길이가 다르면 그 다른 길이만큼의 알파뱃에 큰수부터 부여 길이가 같다면 길이가 같은 문자열이 더 있는지 계속 확인 확인이 끝난 후 각 문자열의 맨 앞에있는 알파뱃을 가지고 누구의 알파뱃이 이웃한 요소에서 먼저 나오는지 확인. 먼저 나오는 알파뱃부터 큰 수 부여 이런 식으로 가장 큰수를 찾아보려 했다.. 하지만..
링크: https://www.acmicpc.net/problem/1783 1783번: 병든 나이트 첫째 줄에 체스판의 세로 길이 N와 가로 길이 M이 주어진다. N과 M은 2,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net 아이디어 n이 1이면 무조건 1칸 n이 2면 m이 4칸이 최대 아니면 (m-1)//2+1만큼 이동 가능 min으로 판단.(4번 이상 움직이려면 모든 방법을 다 한번이상 사용해야 하는데 그러지 못하니 최대가 4칸임) m이 6보다 작거나 같을때 4번 이상으로 움직인다고 하면, 1~4번 방법을 모두 써야 하므로 최댓값은 4가 될 것이고, 최소값은 자신 가로의 길이가 될 것이다. 나머지 세로의 길이가 3 이상이고, 가로의 길이가 7이상인 경우는 4방법을 한 번 ..
링크: https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 아이디어 백트래킹을 통해 수열 구함 방문처리로 본인은 다시 선택하지 못하게 함 remember 변수로 중복되는 수열이 나오지 않도록 구현 구현 import sys input = sys.stdin.readline def dfs(): if len(temp) == m: print(*temp) return remember = 0 for i in range(n): if not visited[i] ..
링크: https://www.acmicpc.net/problem/17144 17144번: 미세먼지 안녕! 미세먼지를 제거하기 위해 구사과는 공기청정기를 설치하려고 한다. 공기청정기의 성능을 테스트하기 위해 구사과는 집을 크기가 R×C인 격자판으로 나타냈고, 1×1 크기의 칸으로 나눴다. 구사 www.acmicpc.net 아이디어 첫 미세먼지의 좌표와 공기 청정기의 좌표를 미리 저장해 둔다. bfs에서 상요한 큐를 이용해 미세먼지를 확산시킨다. 확산된 배열을 복사해서 저장 공기청정기를 작동 위아래 별개로 구현 원하는 만큼 반복은 bfs인자로 t를 넘겨 한 번 확산 청정을 실행할 때마다 -1 t가 0이 되면 미세먼지의 양을 sum을 통해 구해 출력 구현(메모리, 시간 모두 최악) import sys inpu..
