![]()
https://www.acmicpc.net/problem/25497 25497번: 기술 연계마스터 임스 $1$, $2$, $S$ - $K$, $2$로 스킬을 성공적으로 총 4번 사용했다. www.acmicpc.net '하나의 사전 기술은 하나의 본 기술과만 연계해서 사용할 수 있으며, 연계할 사전 기술 없이 본 기술을 사용했을 경우에는 게임의 스크립트가 꼬여서 이후 사용하는 기술들이 정상적으로 발동되지 않는다. 그렇지만 반드시 사전 기술을 사용한 직후에 본 기술을 사용할 필요는 없으며, 중간에 다른 기술을 사용하여도 연계는 정상적으로 이루어진다.' 위의 조건을 정리하면 1. 하나의 사전 기술은 하나의 본 기술과만 연계해서 사용한다. 2. 연계할 사전 기술 없이 본 기술을 사용했을 경우 이후에 사용하는 기..
https://www.acmicpc.net/problem/18429 18429번: 근손실 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 예를 들어 K=4일 때, 3일이 지나면 중량이 488로 www.acmicpc.net 문제 분석 분류 백트래킹, DFS 문제 설명 웨이트 트레이닝을 좋아하는 어떤 대학원생은, 현재 3대 운동 중량 500의 괴력을 소유하고 있다. 다만, 하루가 지날 때마다 중량이 K만큼 감소한다. 다행히도 이 대학원생은 N개의 서로 다른 운동 키트를 가지고 있다. 이 대학원생은 하루에 1개씩의 키트를 사용하며, 매일 어떤 키트를 사용할지 마음대로 결정할 수 있다. N개의 운동 키트에 대한..
![]()
문제 https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 코드 풀이 nxm 크기의 직사각형에서 각 꼭짓점이 같은 숫자인 정사각형의 최대 크기를 찾는 문제이다. 1. 이중리스트를 만들고 정사각형의 최대 크기인 min(n,m)을 temp로 지정한다. 3. arr[i][j]에서 temp까지의 증가하는 k 변수를 만들어서 각 꼭짓점이 같은 숫자인지 확인하고 그 길이를 리스트 안에 저장한다. 4. max(리스트)를 출력한다.
https://www.acmicpc.net/problem/15654 15654번: N과 M (5) N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. N개의 자연수는 모두 다른 수이다. N개의 자연수 중에서 M개를 고른 수열 www.acmicpc.net 백트레킹 개념을 이용하여 문제 풀이를 진행했다. 이때 결과값은 정렬된 상태로 출력해주어야 하므로, go 함수를 호출하기 전에 li를 정렬해준다. M개를 추출을 해야하는 상황에서, arr의 길이가 M과 같아지는 경우(추출 수 충족) 출력 형식에 맞게 출력을 진행해준다. 만약 아직 조건을 충족시키지 못했다면, 아직 arr에 아무것도 없거나 1,1 과 같이 중복 추출이 일어나지 않는 경우 li..
![]()
1. 문제 20410번: 추첨상 사수 대작전! (Easy) 한 줄에 걸쳐 준표가 좋아하는 소수 m, 참가자들이 정한 Seed, 시연으로 공개된 X1, X2 이 주어진다. 항상 가능한 상황만 입력으로 주어진다. www.acmicpc.net 2. 코드 m, seed, X1, X2 = map(int,input().split()) for a in range(100): for c in range(100): if X1 == (a*seed +c)%m: if X2 == (a*((a*seed+c)%m)+c)%m: print(a,c) exit() 3. 풀이 설명이 길어서 어려울거란 생각이 무색하게 제목의easy!에 걸맞게 생각보다 쉬웠다! - 처음에는 a,c 값을 x1과 x2, seed를 통해서 표현해보려했으나 귀납적(?..
14888번: 연산자 끼워넣기 (acmicpc.net) 14888번: 연산자 끼워넣기 첫째 줄에 수의 개수 N(2 ≤ N ≤ 11)가 주어진다. 둘째 줄에는 A1, A2, ..., AN이 주어진다. (1 ≤ Ai ≤ 100) 셋째 줄에는 합이 N-1인 4개의 정수가 주어지는데, 차례대로 덧셈(+)의 개수, 뺄셈(-)의 개수, www.acmicpc.net 문제분석 N개의 수로 이루어진 수열 A1, A2, ..., AN과 수와 수 사이에 끼워넣을 수 있는 N-1개의 연산자(+, -, *, /)가 주어졌을 때, 최대값과 최소값을 구하는 문제다. 이 때, 주어진 수의 순서는 바꿀 수 없고, 식의 계산은 연산자 우선 순위를 무시하고 앞에서부터 차례대로 진행해야 한다. - 입력: 첫째 줄에 수의 개수 N(2 ≤ N..
문제 https://www.acmicpc.net/problem/6603 6603번: 로또 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 수는 k (6 < k < 13)이고, 다음 k개 수는 집합 S에 포함되는 수이다. S의 원소는 오름차순으로 www.acmicpc.net 코드 from itertools import combinations while True: no = list(map(int, input().split())) if no == [0]: break comb = list(combinations(no[1:], 6)) for i in comb: print(*i) print('') 풀이 주어진 숫자 리스트에서 6개의 숫자를 고르는 조합 문제이다..
https://www.acmicpc.net/problem/14501 14501번: 퇴사 첫째 줄에 백준이가 얻을 수 있는 최대 이익을 출력한다. www.acmicpc.net 퇴사[^1] 구현 과정 첫 번째 첫날을 무조건 선택하여 해당 일의 T를 얻어 그다음 가능한 모든 경우의 수를 탐색 구현도 엉망으로 하였고 무엇보다 깔끔하게 받아들여지지 않았다. 두 번째(외부 자료 참고 후) 첫 번째 했던 방식에서 연산을 무시할 경우와 연산에 대해 더 구체화하여 정의하였다 무시할 경우 : if ( i+t[i] ) > day 현재날과 해당 일의 소요일을 더하여 주어진 전체 요일과 크기를 비교한다 하나의 일이 제한된 기간에 수행이 가능함을 나타낸다 연산 : dp[i + t[i]] = max(dp[i + t[i]], dp[..
https://www.acmicpc.net/problem/6443 6443번: 애너그램 첫째 줄에 단어의 개수 N 이, 둘째 줄부터 N개의 영단어가 들어온다. 영단어는 소문자로 이루어져 있다. 단어의 길이는 20보다 작거나 같고, 애너그램의 수가 100,000개 이하인 단어만 입력으로 주 www.acmicpc.net 문제 씬디는 애너그램(anagram) 프로그램을 만들어 줄 수 있는 남자를 좋아한다. 참고로 씬디는 매우 예쁘다. 애너그램 프로그램이란, 입력받은 영단어의 철자들로 만들 수 있는 모든 단어를 출력하는 것이다. 가령 "abc" 를 입력받았다면, "abc", "acb", "bac", "bca", "cab", "cba" 를 출력해야 한다. 입력받은 단어내에 몇몇 철자가 중복될 수 있다. 이 경우 ..
https://www.acmicpc.net/problem/17626 17626번: Four Squares 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1 www.acmicpc.net 문제 라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내..
https://www.acmicpc.net/problem/9207 9207번: 페그 솔리테어 각 테스트 케이스에 대해서, 핀을 움직여서 남길 수 있는 핀의 최소 개수와 그 개수를 만들기 위해 필요한 최소 이동 횟수를 출력한다. www.acmicpc.net 문제 분석 분류 구현, 브루트포스 알고리즘, 백트래킹 문제 페그 솔리테어는 구멍이 뚫려있는 이차원 게임판에서 하는 게임이다. 각 구멍에는 핀을 하나 꽂을 수 있다. 핀은 수평, 수직 방향으로 인접한 핀을 뛰어넘어서 그 핀의 다음 칸으로 이동하는 것만 허용된다. 인접한 핀의 다음 칸은 비어있어야 하고 그 인접한 핀은 제거된다. 현재 게임판에 꽂혀있는 핀의 상태가 주어진다. 이때, 핀을 적절히 움직여서 게임판에 남아있는 핀의 개수를 최소로 하려고 한다. 또..
어떻게 풀어야 할까 항상 문제는 Brute Force를 먼저 생각한다. 문제를 보자마자 어떤 알고리즘을 사용해서 어떻게 풀어야 할지 아는 것이 가능할까. 적어도 나는 안된다... 그렇기 때문에 일단 문제의 정답을 구할 수 있는 알고리즘을 구하고, 문제에서 요구하는 시간 복잡도 안에 해결하기 위해 최적화를 진행한다. 해당 문제는 물에 잠기지 않은 영역의 갯수 중 최대값을 구하는 문제이다. 물의 높이는 선형적으로 점차 증가하고, 각각의 경우의 수를 기록하여 그 중 최대값을 출력하면 된다. 물에 잠기지 않는 안전 영역은 DFS를 통해서 구할 수 있다. DFS를 통해 연결 요소를 각각의 영역에서 반복한다, 즉 안전 영역의 갯수를 물에 아직 잠기지 않고, 방문한적 없는 모든 영역에서 DFS를 통해 DFS가 실행되..
