Simple Explain

점점 조건이 변화하는 순열구하기 문제라고 생각하면 된다 15649번 1~N 까지 중복없이 순열고르기 https://www.acmicpc.net/problem/15649 - 중복되는 수 없이 -> visited 리스트를 통한 방문 기록 15649번: N과 M (1) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net N, M = map(int, input().split()) nums = [x for x in range(1, N+1)] output = [] visited = [False]*N def solve(depth, N, M): if dep..

#15663번 N과M (9) https://www.acmicpc.net/problem/15663 15663번: N과 M (9) 한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해 www.acmicpc.net 비슷한 유형의 문제를 연달아 풀고 있는 중이다. N, M = map(int, input().split()) nums = sorted(list(map(int, input().split()))) output = [] visited = [False]*N def solve(depth, n, m): if depth == m: r = ' '.join(map(str, output..

15654번 N과 M (5) https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 음... 완전탐색을 위해서 for문을 중첩으로 돌려야 하는데 for 문을 중첩시키는 횟수를 입력받아서 능동적으로 변경해야 하는 상황이었다. 이ㅓㄱㄹ 어떻게 하나..? 했더니 답은 재귀였다. 즉, 입력값에 맞춰서 for문의 중첩횟수를 설정해줘야 하는 경우라면 재귀함수가 적합하다 import sys N, M = map(int, input().split()) num..

#6064번 카잉달력 https://www.acmicpc.net/problem/6064 6064번: 카잉 달력 입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. www.acmicpc.net 부르트포스 알고리즘이라서 무조건 1씩 더해주면서 연산을 진행하려고 했다. -> 시간초과 머리를 굴리다가 도저히 답이 안나와서 또 검색 포인트는 문제를 탐색하는데 들어가는 시간을 어떻게 최소화 시킬 것인지다. M, N, x, y가 순차적으로 입력되고 K를 구하는 형태인데 K에서 x를 빼면 M의 배수이다. 또 K에서 y를 빼면 N의 배수이다. 이 말은 즉 x나 y 둘 중 하나의 값에..

#14500번 테트로미노 https://www.acmicpc.net/problem/14500 14500번: 테트로미노 폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변 www.acmicpc.net 일단 몇 가지 개념을 짚고 넘어가자. 먼저 지금 계속 하고있는 브루트포스 (brute force) : 완전탐색 알고리즘. 가능한 모든 경우의 수를 탐색하면서 요구조건에 맞는 결과를 가져옴 그리고 이와 비슷한 개념인 백트래킹(Backtracing) : 되추적 이라는 의미. 이전 단계로 거슬러 올라가 다른 가능성을 찾는 방법. 모든걸 찾아보는 점에서는 브루트포스와 비슷하나 그..

#1107 리모컨 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net 이것도 쓸데없는 고민을 참 많이했다. 난 좀 단순하게 생각해볼 필요가 있을 듯 하다. simple is best!! target = int(input()) n = int(input()) broken = [] if n > 0: broken = input().split() answer = abs(target-100) for num in range(1000001): f..

브루트 포스 단계에 접어들었다. 그냥 완전탐색. 모든 경우를 체크하는 상황이라고 보면 된다. 처음 막힌 문제는 #3085 사탕게임 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 처음에는 진짜 열심히 고민하고 또 고민했는데 브루트 포스다. 그냥 쉽고 간단하게 생각하면 된다. import sys input=sys.stdin.readline def check(arr): n=len(arr) answer=1 for i in range(n): # 열 순회하면서 연속되는 숫자 세기 cnt=1 for j in range(1, n): if arr[i][j] == arr[i][..

#2133번 타일채우기 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 이번의 타일은 3줄짜리다!.. 여러 점화식을 고민해봤지만 결론은 다음과 같다. n==2일 때는 3가지 경우가 가능하다. 대충 이런 느낌으로 세 개. 문제는 그 다음부터인데 일단 홀수 줄의 타일의 경우에는 불가능하다 -> 0 짝수 일 때만 가능하기 때문에 다음 케이스는 dp[4]가 되는데 이 때는 dp[2]에서 구해놓은 3가지 케이스 중 두개를 중복을 허용해서 골라주면 된다. -> 3*3 = 9 단, 4줄의 타일일 경우에는 새로운 모양이 생겨나는데 바로 이런 형태이다. 총 2가지 경우가..

먼저 2차원 리스트 생성시 진행한 실수부터 짚고 넘어가자 dp = [[0]*n]*2 이짓거리 했더니 dp[0]과 dp[1]이 동시에 변경된다. (하나만 접근해도). 아마 주소가 복사되는 형태인 듯 하다. 그래서 dp = [[0]*n for x in range(2)] 이렇게 해줘야한다. 한참 머리가 아팠다.. 보통의 언어들은 call by value / call by reference 둘 중 하나를 취한다. 값을 설정할 때 a = 2 b = a 이렇게 진행 할 경우 b에 2라는 값(value)이 저장되면 call by value가 되고 a의 메모리 주소(reference)가 저장되면 call by reference가 된다. 이를 어떻게 알 수 있냐면 b를 수정해보면 된다. b를 수정했을 때 a도 동시에 수..

DP의 늪에서 벗어나질 못하는중.... #2156번 포도주 시식 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 1차원 행렬에 있는 숫자를 최댓값이 되도록 선택하는 문제이다. 조건은 딱 하나 연속으로 3개의 수를 선택할 수 없다는 점. 약간 골치아팠던 문제이다. import sys n = int(sys.stdin.readline()) wines = [] for i in range(n): wines.append(int(sys.stdin.readli..