링크: https://www.acmicpc.net/problem/9375 아이디어규칙을 찾아 식으로 표현해보자하나라도 입고있으면 되고 같은 종류의 옷은 2개이상 못입는다.옷 종류별로 개수를 구한 후 + 1 하고 서로 곱하면 조합할 수 있는 모든 경우의 수가 된다.모자가 3개있으면 각 모자를 모두 쓰는 경우 + 안쓰는 경우 이렇게 존재입력받는 옷을 종류를 기준으로 갯수를 저장한다.갯수는 딕셔너리 형태로 {hat: 3} 과같이 저장한다.이후 위에서 구한 식을 통해 조합 할 수 있는 전체 경우의 수를 구한다.알몸인 경우 1을 빼면 알몸이 아닌 모든 경우의 수를 구할 수 있다. 구현test_case = int(input())for i in range(test_case): n = int(input()) ..
링크: https://www.acmicpc.net/problem/3568 아이디어입력받은 문자열을 " "(공백) 단위로 잘라 리스트로첫 요소는 무조건 맨 앞에 고정으로 사용하기 때문에 따로 저장.2번때 요소부터 for 문을 돌리며 판별 진행요소의 뒤에서 부터 확인하는데 맨 뒤는 , 아니면 ; 이기 때문에 그 다음 부터 확인 *이거나 &이면 따로 저장한 첫번째 요소의 뒤에 붙인다.]이 나오면 []를 붙이고 for문을 한번 건너 뛰어 다음으로 간다.알파벳 소문자가 나올 때까지 반복한다.알파벳 소문자가 나오면 그 지점을 가지고 변수명을 추출한다. -> 요소[:그지점 +1] = 변수명! 구현li = input().split()fix = li.pop(0)for i in li: result = fix f..
링크: https://www.acmicpc.net/problem/1929 생각M, N을 입력받음M부터 N까지 반복문을 돌며 소수 판별소수는 무엇인가 -> 약수를 1과 자기 자신만을 가지는 수하나의 수를 num이라 할 때 2부터 num -1 까지의 수를 눴을 때 나머지가 0이 되는 경우가 있으면 소수가 아님2중 for문을 써야겠다구현 1 - 시간초과M, N = map(int, input().split(" "))result = []for num in range(M, N+1): if num > 2: for i in range(2, num): if num % i == 0: break if i == num-1: ..
링크: https://www.acmicpc.net/problem/1449 1449번: 수리공 항승 첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 www.acmicpc.net 아이디어 물이 새는 곳 리스트를 돌며 처음것과 다음것의 차를 구하여 저장 -> tmp 그 값이 L보다 작으면 L-tmp를 하여 저장 -> L1 계속 돌며 L1-tmp를 하다가 tmp가 L1보다 더 커지는 경우 테이프를 하나 더 가져와야 함 cnt += 1 반복문이 끝날 때까지 계 구현 import sys input = sys.stdin.readline N, L = map(i..
링크: https://www.acmicpc.net/problem/21736 21736번: 헌내기는 친구가 필요해 2020년에 입학한 헌내기 도연이가 있다. 도연이는 비대면 수업 때문에 학교에 가지 못해 학교에 아는 친구가 없었다. 드디어 대면 수업을 하게 된 도연이는 어서 캠퍼스 내의 사람들과 친해지고 www.acmicpc.net 아이디어 I의 좌표를 찾고 그 지점부터 BFS진행 P를 만나면 cnt +1 X가 아닌 부분을 만나면 X로 바꿔주고(방문처리) 큐에 좌표를 넣어준다. BFS탐색이 끝난 후 cnt값을 return return된 값이 0이면 TT 아니면 값 그대로 출력 구현 import sys input = sys.stdin.readline from collections import deque dy..
링크: https://www.acmicpc.net/problem/1182 1182번: 부분수열의 합 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 아이디어 백트래킹으로 요소를 선택하며 합한 수를 tmp에 저장 tmp가 s와 같아지면 cnt + 1 백트래킹 함수의 인자로 현재 더한 요소 인덱스+1로 넘겨주어 그다음 요소부터 선택하게 설계 구현 import sys input = sys.stdin.readline def back(idx): global tmp, cnt if tmp == s: cnt += ..
링크: 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번 장대 ->..
