링크: https://www.acmicpc.net/problem/10819 아이디어N의 크기가 3가능한 모든 경우의 수를 다 계산해도 (가능한 모든 수열)! *(비교횟수) = 8! * 8 = 얼추 32만 모든 경우를 다 보고 비교해도 충분할 것 같음.permutations 함수로 가능한 모든 수열을 다 구하고앞뒤 요소 합 연산 을 진행결과값을 이전 연산값과 비교하며 최대값을 찾자구현# 모든 경우를 다 비교해봐도 될듯# N의 최대 크기가 8이라 다 비교해도 8! * 8 는 얼추 32만번 임 충분from itertools import permutationsN = int(input())lis = list(map(int, input().split()))result = 0for li in permutations(..
링크: https://www.acmicpc.net/problem/16924 아이디어*로 십자가를 만드는게 요지가 아니였음십자가로 입력된 격자를 완성 할 수 있냐 없냐가 주 요구사항이다십자가로 만든 격자를 표시해야 할 리스트 하나를 만들고 가자* 위치를 1로 지정하고 나머지를 0으로 해두자이제 * 위치를 기준으로 만들 수 있는 십자가를 탐색하고 표시용 리스트애 표시하자size크기로 중간 기준 상 하 좌 우 좌표의 값이 유효한 위치인지 또한 *이 맞는지 판별아니라면 바로 return으로 함수 종료십자가가 완료됐다면십자가의 중심 좌표를 저장그 십자가 영역의 좌표를 표시 리스트에 표시 (1->0)size를 키워가며 모두 탐색check 리스트를 판단하고 모든 영역이 채워지지 않았으면 -1 출력 후 종료무두 채워..
링크: https://www.acmicpc.net/problem/2877 아이디어그냥 2진수 생각하면 너무 쉬울 거 같다4는 0 1은 7로 생각하고 풀어보자우선 몇자리수인지 판단하자1자리 - 2개2자리 - 4개3자리 - 8개이런 식의 규칙을 가진다 중복합을 통해 몇자리인지 판단해아할듯자릿수를 구한 후 그 자리수에서 몇번째의 수인지 한번 더 판단입력값 K에서 누적합을 진행합 값을 빼고 -1을 해준다-1을 해줘야 하는 이유는 0000과 같은 경우도 하나의 경우로 쳐야하기 때문몇번째 수인지 구했으면 이를 2진수 변환을 진행 자릿수도 구한 값으로 지정하여 생성변환된 2진수를 0을 4로 1을 7로 변환한다.그럼 끝~!구현# 뭐야 2진수로 생각하면 쉬울듯# 몇자린지 구하고 거기서 몇번째인지 판단하면 끝K = int..
링크: https://www.acmicpc.net/problem/12933 아이디어현재 문자가 해당 오리에게 올 차례인지 확인각 배열의 길이를 통해 몇번째 문자가 올지 판단하면 될듯맞는 오리를 찾아 해당 문자 추가오리 울음이 완료되면 해당 오리를 ("")로 처리문자를 넣을 수 있는 오리를 못 찾았는데 그 문자가 q이면 배열 생성q가 아니면 -1 반환모든 문자를 순회하며 동시에 울고 있는 오리 수를 추적하고 그 최대값 저장구현sound = list(input())li = [] # 각 오리의 울음 진행 상태를 저장하는 리스트max_cnt = 0for tmp in sound: placed = False for j in range(len(li)): now = li[j] ..
링크: https://www.acmicpc.net/problem/15787 아이디어단순 구현으로 각 상황 구현자리 한칸씩 밀기는 슬라이싱으로 자르고 앞이나 뒤에 [0] 더해주면 될듯마지막 중복된 패턴을 거르는건 set 사용 구현import sysinput = sys.stdin.readlineN, M = map(int, input().split())train = [[0]*20 for _ in range(N)]for i in range(M): tmp = list(map(int, input().split())) if tmp[0] == 1: if train[tmp[1]-1][tmp[2]-1] == 0: train[tmp[1]-1][tmp[2]-1] = 1 ..
링크: https://www.acmicpc.net/problem/16173 아이디어가장 빠르게 목적지에 가능한 경우가 있는지 확이해야하기 때문 BFS진행방문 확인용 배열 사용bfs 진행 중 목적지에 도착시 바로 탐색 종료 후 "HaruHaru" 출력탐색이 완료된 후에도 목적지에 도착하지 못할시 "Hing" 출력 구현# (0,0) 출발# 범위 안에서만 이동# 오른쪽 아래로만 이동 가능# 가장 오른쪽 가장 아래 도착 = 승리# 이동가능 수는 밟고있는 칸의 수 만큼 무조건 이동import sysfrom collections import dequeinput = sys.stdin.readlinedef bfs(i, j): q = deque() q.append((i, j)) visited = [[Fa..
링크: https://www.acmicpc.net/problem/1759아이디어 비밀번호의 모든 가능한 조합을 탐색해야 하므로 백트래킹을 사용알파벳은 사전 순으로 정렬되어야 하므로 입력받은 알파벳 리스트를 정렬한 후 탐색을 시작백트래킹 함수는 매개변수로 현재 인덱스를 받아 해당 인덱스 이후의 문자들만 탐색패스워드의 길이가 L이면 해당 문자열이 유효한 비밀번호인지 check 함수를 통해 확인모음이 최소 1개자음이 최소 2개조건을 만족하면 해당 비밀번호를 출력하고 만족하지 않으면 그대로 return 구현import sysinput = sys.stdin.readlinedef check(password): mo = sum (1 for x in password if x in 'aeiou') ja = l..
링크: https://www.acmicpc.net/problem/1182 아이디어모든 경우의 수를 탐색하는 문제이므로 백트래킹을 활용한다.back 함수는 인자로 idx와 li_sum을 받는다.idx는 현재 탐색할 수열의 인덱스를 의미하며, 이를 통해 a + b 와 b + a 같이 중복되는 조합을 방지할 수 있다.li_sum은 지금까지 선택한 수들의 합이며, 이 값을 s와 비교해 조건을 만족하는지 판단한다.현재 합이 s와 같으면 cnt를 1 증가시킨다.하지만 여기서 탐색을 멈추는 것이 아니라 이후 값을 더한 경우도 여전히 조건을 만족할 수 있으므로 재귀를 이어간다.다만 s == 0인 경우 아무 값도 선택하지 않은상태에서 li_sum == s가 성립하므로 마지막에 cnt에서 1을 빼준다.구현import ..
링크: https://www.acmicpc.net/problem/15651 아이디어이전글 N과 M (1) 을 보고오면 더 쉽다.N과 M (1)과 유사하지만 조건 하나만 빼주면 위 문제가 풀린다.N과 M (1)에선 check 배열에 존재하면 추가하지 않았지만 이는 중복을 허용해야 하기 때문에 그 조건을 제거해준다.구현import sysinput = sys.stdin.readlinedef back(): if len(check) == m: print(*check) return for i in range(1, n+1): check.append(i) back() check.pop()n, m = list(map(int, input().spli..
