문제 https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 풀이 #중간에 나오는 수가 모두 0 이상 20 이하이어야 한다 # 백준 5557 N = int(input()) List = list(map(int,input().split())) DP= [[0 for _ in range(21)] for _ in range(N+1)] for i in range(N): if i==0: DP[i][List[0]] = 1 else: for j in range..
Koala - 14기/코딩테스트 준비 스터디
ㅣ전깃줄 !https://d2gd6pc034wcta.cloudfront.net/tier/11.svg 시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율 1 초 128 MB 37655 18072 14540 47.660% 문제 두 전봇대 A와 B 사이에 하나 둘씩 전깃줄을 추가하다 보니 전깃줄이 서로 교차하는 경우가 발생하였다. 합선의 위험이 있어 이들 중 몇 개의 전깃줄을 없애 전깃줄이 교차하지 않도록 만들려고 한다. 예를 들어, 과 같이 전깃줄이 연결되어 있는 경우 A의 1번 위치와 B의 8번 위치를 잇는 전깃줄, A의 3번 위치와 B의 9번 위치를 잇는 전깃줄, A의 4번 위치와 B의 1번 위치를 잇는 전깃줄을 없애면 남아있는 모든 전깃줄이 서로 교차하지 않게 된다. https://u..
https://www.acmicpc.net/problem/2651 2651번: 자동차경주대회 첫째 줄에는 정비를 받지 않고 갈 수 있는 최대 거리가 주어진다. 둘째 줄에는 정비소의 개수가 입력되는데 정비소 수는 100개 이하이다. 셋째 줄에는 인접한 정비소 사이의 거리가 차례로 주어 www.acmicpc.net 문제 분석 난이도 골드 4 분류 구현, DP 들어가기 전에 DP이지만 입력이랑 예외처리가 상당히 까다로운 문제, 최소값만 구하는 것이라면 별로 어려운 문제가 아니지만 개수구하기 + 역추적 까지 해야하는 문제 문제 풀이 문제 해결을 조금 더 수월하게 하기 위해서 거리를 누적해서 저장해 주었다. 현재 지점과 선택한 지점의 누적된 값을 빼면 거리를 구할 수 있고 그 거리가 k보다 작다면 대소비교를 하고..
https://www.acmicpc.net/problem/1051 1051번: 숫자 정사각형 N×M크기의 직사각형이 있다. 각 칸에는 한 자리 숫자가 적혀 있다. 이 직사각형에서 꼭짓점에 쓰여 있는 수가 모두 같은 가장 큰 정사각형을 찾는 프로그램을 작성하시오. 이때, 정사각형은 행 www.acmicpc.net 코드 n, m = map(int, input().split()) arr = [] for i in range(n): arr.append(list(input())) check = min(n, m) answer = 0 for i in range(n): for j in range(m): for k in range(check): if ((i + k) < n) and ((j + k) < m) and (arr..
문제 https://www.acmicpc.net/problem/1058 Algorithm 직접 친구라면 2-친구이다.( 거리 = 1) 혹은 내가 어떠한 대상 A와 2-친구가 되려면, A와 직접 친구인 누군가와 직접 친구여야 한다. (거리 = 2) 위 두 조건 중 하나라도 만족하면 2-친구이다. 즉, 나와 대상의 거리가 2 이하라면 2-친구이다! 이제 BFS를 돌리면 된다. Code #include using namespace std; #define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0); typedef long long ll; typedef pair pii; typedef pair pll; int n; vector graph[51]; bool visi..
문제 링크 https://www.acmicpc.net/problem/15684 15684번: 사다리 조작 사다리 게임은 N개의 세로선과 M개의 가로선으로 이루어져 있다. 인접한 세로선 사이에는 가로선을 놓을 수 있는데, 각각의 세로선마다 가로선을 놓을 수 있는 위치의 개수는 H이고, 모든 세로선 www.acmicpc.net 접근 방법 추가해야하는 가로선이 3개 보다 많거나 불가능할 경우 모두 -1을 출력하라는 요구사항이 있기 때문에 3가지를 넘어가는 경우에 대해선 생각하지 않아도 되고, N과 H 또한 각각 최대 10, 30으로 크지 않아서 최악의 경우에 대해 ((N-1) * H) C 3 = 3,244,140 개의 조합만을 구하면 되기때문에 백트래킹을 이용하여 완전 탐색하는 방법을 생각했습니다. 개인적으로..
문제 소스코드 from collections import deque from itertools import combinations n,m=map(int,input().split()) map = [list(map(int,input().split())) for i in range(n)] arr = map[:] ans = 0 dx=[0,0,1,-1] dy=[1,-1,0,0] def virus(): q = deque() # 위에서부터 맵을 돌다가 2를 만나면 바이러스를 퍼뜨림 for i in range(n): for j in range(m): if arr[i][j] == 2: q.append((i,j)) while q: x,y=q.popleft() for i in range(4): nx = x+dx[i] ny=..
문제 https://www.acmicpc.net/problem/2503 2503번: 숫자 야구 첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트 www.acmicpc.net 풀이 한줄 요약: 영수가 추측한 수와 strike, ball를 통해서 가능하지 않은 수들을 걸러냄!! 0~999 중에 제거 1. 한 숫자 안에 같은 숫자 있는 수 2. 어떠한 자리에라도 0이 들어가는 수 3. 영수가 추측한 수와 제시된 strike, ball수와 맞지 않는 수 123~999까지의 숫자와 영수가 예측한 숫자의 strike(자리수 같고 숫자 같고)수와 ball(자리수 다르고 숫자..
문제 요약 N개의 수와 N-1개의 연산자가 주어졌을 때, 만들 수 있는 식의 결과가 최대인 것과 최소인 것을 구하는 프로그램 입력 첫째 줄에는 수의 개수가 주어지고, 둘째 줄에는 수가 주어지며, 셋째 줄에는 4개의 연산자의 각각 사용 가능한 개수가 주어진다 ex) 2 5 6 0 0 1 0 출력 첫째 줄에 최대값을, 둘째 줄에 최소값을 출력한다. ex) 30 30 문제 코드 코드 설명 5번 줄까지는 입력을 받는 부분이니 굳이 설명하지 않겠음. go 함수 재귀함수로 매개변수로 받는 add, sub, mul, div의 남은 개수를 파악하고 이에 따라서 다음 연산을 진행한다. 더이상 사용할 연산자가 없으면 계산 값을 res_l에 할당하고 재귀적으로 실행됐던 부분을 반대로 돌아간다. 이후 다른 순서로 또 재귀적으..
알고리즘 범위에 해당하는 숫자들이 자릿수마다의 중복되는지 체크하면 된다. 같은 값이 있는지 확인하는 방법으로는 딕셔너리를 떠올렸고 아래와 같이 중복 체크를 해주었다. for item in hotel: d={'0':0, '1':0, '2':0, '3':0, '4':0, '5':0, '6':0, '7':0, '8':0, '9':0} flag=True for s in str(item): if s in d.keys(): d[s] += 1 for v in d.values(): if v >= 2 : flag=False if flag: ans.append(item) 전체 코드 while True: try: n,m=input().split() hotel=list(range(int(n),int(m)+1)) ans=[] ..
문제 https://www.acmicpc.net/problem/1855 1855번: 암호 준표와 세준이는 서로 솔루션을 토론 하면서 다른 사람이 자신들의 솔루션을 듣지 못하게 하도록 서로 메시지를 주고받을 때 메시지를 암호화 하여서 주고받았다. 암호를 만드는 방법은 다음과 www.acmicpc.net 코드 #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long long using namespace std; char arr[20][20]; int main() { ios::sync_with_stdio(false); cin.tie..
문제 분석 입력의 형태는 주사위의 전개도 값을 주어진다. 이때 주사위의 값의 패턴이 없기 때문에 주사위가 쌓일 때 바닥과 천장의 값을 직접 찾아야 하고 같은 이유로 측면에 놓이는 값들을 구해야한다. 한 쪽 측면에 놓이는 값들의 합중에서 가장 큰 수를 원하기 때문에 한개의 주사위의 옆면에 해당하는 값들중 가장 큰 수만 선정하면 된다. 즉 주사위를 쌓는 경우에 대해서 찾으면 값은 알 수 있게 된다는 의미이다. #include #include using namespace std; // 아래면의 인덱스를 윗면으로 단순히 바꿔줌 int top_val(int index) { if (index == 0) return 5; if (index == 1) return 3; if (index == 2) return 4; i..
