코테 탈출일지

https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net 접근 방식 - 주어진 사탕 정보 배열에서 연속인 최대 사탕수를 세는 방법 고민 - 사탕의 색이 다른 인접한 두 칸을 서로 교환하는 방법 고민 코드 풀이 n = int(input()) # 보드의 크기 candy = [list(input()) for _ in range(n)] # 사탕 색깔 정보 di = [1, 0] # 우하향 방향으로 탐색, 인접 사탕을 바꾸는 데 필요 dj = [0, 1] answer=0 cnta, cntb = 1, 1 # 가로, 세로의 연속 사탕 개수 count def check(graph, n)..

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 접근 방식 - 재귀를 통해 아직 방문하지 않았으며, 방문할 수 있는 도시를 순차적으로 방문하는 dfs 구현 - 이때 최소비용을 더하는 방법, 방문처리 해주는 방법 고민 - 시작점이 어느 도시인지가 유효한지 고민 코드 풀이 n = int(input()) # 도시의 수 cost = [list(map(int, input().split())) for _ in ..

https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 접근 방식 - 하나의 질문/대답 정보를 통해 유추할 수 있는 숫자들의 풀을 차례로 조사하여 교집합 처리해주는 방식 - or 가능한 전체 경우의 수에서 하나의 질문/대답 정보를 통해 불가능한 숫자를 차례로 제외해주는 방식 코드 풀이 위의 접근방식 중 첫 번째 방식은 하나의 질문/대답에서 고려해야 하는 순열, 조합의 경우의 수가 너무 복잡하여 두 번째 방식을 활용하였습니다. 두 번째 방식은 차례대로 ..

https://www.acmicpc.net/problem/10819 10819번: 차이를 최대로 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다. www.acmicpc.net 접근 방식 - 주어진 숫자들의 모든 배열 경우의 수 탐색 방법 (개별 숫자 단위, 전체 배열 단위 등) 코드 풀이 from itertools import permutations n = int(input()) nums = list(map(int, input().split())) ans = [] for nums_per in permutations(nums): sums = 0 for i in range(n-1): #..

https://www.acmicpc.net/problem/2003 2003번: 수들의 합 2 첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다. www.acmicpc.net 접근 방식 - 수열의 부분합을 처리할 수 있는 효율적인 탐색 방법 고안 - 복잡도를 낮출 수 있는 방법 고민 코드 풀이 n, m = map(int, input().split()) nums = list(map(int, input().split())) cnt = 0 start, end = 0, 0 # nums[start:end] 방식으로 접근 (투 포인터 알고..

https://www.acmicpc.net/problem/14888 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, 곱 www.acmicpc.net 접근 방식 - 연산자를 끼워놓는 조합의 수와 이를 기술적으로 구현하는 방법 - or 백트래킹(dfs) 코드 풀이 n = int(input()) num = list(map(int, input().split())) op = list(map(int, input().split())) maxi = -1e9 # 초기 값, 재귀를 거치며 최대값이 계속..

https://www.acmicpc.net/problem/14889 14889번: 스타트와 링크 예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다. www.acmicpc.net 접근 방식 - 팀 분배를 하는 모든 조합을 구현하는 루프 고안 - 하나의 팀 분배 경우의 수에서 능력치의 차이 구하는 방법 고안 코드 풀이 from itertools import combinations n = int(input()) graph = [list(map(int, input().split())) for _ in range(n)] # 함수를 통해 start 팀의 인덱스, link 팀의 인덱스가 주어졌을때 그 차..

https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 접근 방식 - 효율적인 그래프 검사 방법 구상 - 함수 활용 여부 고민 코드 풀이 n, m = map(int, input().split()) graph = [] for _ in range(n): tmp = list(input()) graph.append(tmp) s_max = min([n, m]) # 가능한 정사각형의 최대 변의 길이 def check(graph, s): flag = 0 for i..