문제https://www.acmicpc.net/problem/31229문제 설명 다음 조건을 만족하는 길이 N의수열 $A=\left\{A_{1},A_{2},\dots,A_{N}\right\}$를 출력한다.  $1\leq i을 만족하는 모든 정수 i와 j에 대해 다음 조건을 만족한다.  $A_{i}\neq A_{j}$이고 수열 A의모든 원소는 $1$이상 $10^9$ 이하의 정수이다.$A_{i}+A_{j}$는 $A_{i}\times A_{j}$의 약수가 아니다. 풀이문제부터 해석해보자. $A_{i}\neq A_{j}$일 때, i번째 수는 j번째 수와 달라야 하므로 j기준 왼쪽의 수는 모두 j와 달라야 하고 그 왼쪽의 수는 본인보다 더 왼쪽에 있는 수와 서로 달라야 한다. 즉 모든 수는 서로 다르다.  $A..

문제https://www.acmicpc.net/problem/20207문제 설명일년의 날짜가 1일부터 365일로 표시되어있는 달력이 존재한다.달력에 일정이 있는 곳에만 조건에 부합하게 코팅지를 달력에 붙일 것이다.연속된 두 일자에 각각 일정이 1개 이상이 있다면 이를 일정이 연속되었다고 표현한다.연속된 모든 일정은 하나의 직사각형에 포함되어야 한다.연속된 일정을 모두 감싸는 가장 작은 직사각형의 크기만큼 코팅지를 오린다.달력은 다음과 같은 규칙을 따른다.일정은 시작 - 종료날짜를 모두 포함한다.시작일이 같을 경우 일정의 기간이 긴 것이 먼저 채워진다. 시작일이 가장 앞선 일정부터 차례대로 채워진다.일정은 가능한 최 상단에 배치된다.일정 하나의 세로의 길이는 1이다.하루의 폭은 1이다.잘라야 하는 ..

문제https://www.acmicpc.net/problem/10653문제 설명총 N개의 체크포인트로 구성되어 있는, 마라톤 코스가 존재한다.1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야 마라톤이 종료된다.게으른 박승원은 몰래 K개의 체크포인트를 몰래 건너뛰려 한다.단 1번 체크포인트와 N번 체크포인트는 건너뛰지 않는다.최대 K개를 건너뛰면서 달릴 수 있을 때, 달려야 하는 최소 거리를 구한다.점 (x1,y1)과 (x2,y2) 점 간의거리는 |x1-x2| + |y1-y2| 이다. 풀이문제를 이해해보자. N개의 체크포인트가 있고, 최대 K개를 건너뛰면서, 1번에서 N번으로 이동해야한다.총 1,2,3,4,5의 노드가 있으면 1 -> 3 -> 5 혹은 1 ->..

문제https://www.acmicpc.net/problem/1368문제 설명N개의 논에 물을 대려고 한다. 물을 대는 방법에는 두 가지가 있다. 직접 논에 우물을 판다.이미 물을 대고 있는 다른 논으로부터 물을 끌어온다.각각의 논에 대해 우물을 파는 비용과, 논들 사이에 물을 끌어오는 비용들이 주어졌을 때, 모든 논에 물을 대는데 필요한 최소비용을 출력한다. 풀이0 2 2 22 0 3 32 3 0 42 3 4 0위 같은 배열이 주어졌다고가정하자. 4개의 논에 물을 대야 한다.예시 경우를 만들어 보면 , 1 -> 3 -> 2 -> 4, 1 -> 4 -> 2 -> 3 등 많은 경우의 수가 존재할 것 이다. 따라서 나는 A에서 B로 갈 수 있는 최소의 가중치를 찾는 것이라 생각했고, 플로이드 워셜로 초기..

문제https://www.acmicpc.net/problem/23841문제 설명N*M크기의 보드가 주어진다.보드를 좌우 방향으로 반으로 포개어 접어 데칼코마니를 만든다.이 때 데칼코마니 결과를 출력한다. 풀이단순하게 좌우를 대칭하면 해결되는 문제이다. C의 길이가 주어졌기때문에 board를 완전 탐색하여 해당 위치에 물감이 있다면C - curr_col-1(인덱스는 0부터 시작하므로 1을 더 감소한다.)을 통해 대칭되는 위치에 값을 갱신했다. board를 완전 탐색한다.해당 위치가 '.'이 아니라면, C - c(현재 위치) -1의 위치에 현재 물감 색을 갱신한다.결과를 출력한다.코드import sysinput = sys.stdin.readlineR,C = map(int,input().split())boar..

문제https://www.acmicpc.net/problem/25551문제 설명포닉스는 흰색 또는 검은색의 마스크, 티셔츠, 바지만을 입는다.마스크와 티셔츠는 다른 색이어야 한다.티셔츠와 바지 역시 다른색이어야 한다.이틀 연속으로 같은 색의 티셔츠를 입지 않는다.한번 착용한 마스크, 티셔츠, 바지는 다시 사용하지 않는다.포닉스가 가진 각각의 개수가 주어질 때, 연속해서 옷을 고를 수 있는 최대 일수를 구하라. 풀이포닉스가 가질 수 있는 옷의 종류는 검정과 흰색이다. 이를 W,B로 표현하자. 위에부터 순서대로 마스크, 티셔츠, 바지는 각각 연속해서 색이 겹치면 안되고, 최대 1회만 입을 수 있다. 그렇다면 나올 수 있는 조합은 (a) W-B-W or (b) B-W-B이다.따라서 순서대로 개수가 주어지면 ..

문제https://www.acmicpc.net/problem/5376문제 설명유리수 분수를 소수로 나타내면 유한 소수와 무한 소수로 나타낼 수 있다.소수를 입력받은 뒤, 이를 분수로 나타내라 풀이소수를 분수로 변환하는 과정은 중학생 때 배웠던 기억이 있다.유한 소수라면 단순히 분자 / 분모를 하면 되지만, 무한 소수라면 말이 다르다. 예시를 들어보자.0.333333...이라는 무한소수가 존재한다. x = 0.333....이라고 가정하자.그렇다면 10x = 3.333....이 될 것이다.즉 10x - x = 3.333... - 0.333... = 3, 9x = 3, x = 1/3이다. 즉 무한소수를 분수로 변환하는 방법은 무한으로 되풀이 되는 부분을 제거하면 된다.따라서 무한으로 반복되는 부분의 소수의 첫..

문제https://www.acmicpc.net/problem/25757문제 설명 세 종류의 미니게임을 플레이한다.Y(윷놀이), F(같은 그림 찾기), O(원카드) 세 종류의 게임은 각각 2, 3, 4명이서 플레이하는 게임이다.각 게임은 인원수가 부족하면 게임을 시작할 수 없다.N개의 플레이 신청과, 플레이 게임의 종류가 주어질 때 최대 몇 번이나 게임을 플레이 가능한지 구한다.한 번 같이 플레이한 사람과 다시 플레이하지 않는다. 풀이중복으로 같은 플레이어가 들어올 수 있으니 딕셔너리에 참가 신청 명단을 저장했다.그 후 각 게임에 필요한 인원만큼 계산하여 총 플레이 횟수를 구했다. 초기에 각 게임을 1,2,3으로 매핑한다.(게임 당 필요한 인원 수)전체 플레이어의 수 // 필요한 인원 수를 통해 총 게임..

문제https://www.acmicpc.net/problem/11564문제 설명 수직선상에 초콜릿이 존재한다.초콜릿은 a 이상 b 이하의 모든 정수 좌표 위에 존재한다.점프력이 K인 준민이는 항상 점프 거리가 K가 되도록 점프한다.0에서 시작해서 최대 몇 개의 초콜릿을 얻을 수 있는지 구한다. 풀이단순 수식 계산 문제라고 생각했다.먼저 두 숫자가 0을 기준으로 한쪽에 몰려있는지 판단했다. 만약 하나는 음수, 하나는 양수라면, 0의 위치에 초콜릿을 먹고 시작한다. 그 후 각각 0을 기준으로 a의 배수, b의 배수만큼 초콜릿을 먹을 수 있다. 두 숫자 모두 양수 혹은 음수라면 사이에 존재하는 초콜릿을 판별하여 결과에 합산했다. A*B가 음수일 때두 수의 절댓값을 K로 나누어 초콜릿의 수를 구한다.A*B가 ..

문제https://www.acmicpc.net/problem/16940문제 설명정점의 개수가 N개, 1부터 N까지 번호가 매겨져있는 양방향 그래프가 존재한다.노드의 탐색 순서가 입력으로 주어진다.BFS 알고리즘을 실행했을 때 가능한 탐색 순서가 맞는지 확인하는 스폐셜 저지 문제를 만들어야 한다.주어진 입력이 올바른 방문 순서인지 검사한다. 풀이처음엔 BFS 탐색을 통해 깊이 별 노드들을 담아 순서가 맞는지 탐색하려고 했다.하지만 문제가 1개 있었다. 같은 깊이지만 서로 다른 노드에서 뻗어진 자식이라면 부모의 순서에 따라 자식의 방문 순서도 생긴다는 것이다.따라서 슬라이딩 윈도우를 이용하여, 방문 순서를 탐색했다.s = 부모 노드e = 자식 노드s가 e를 자식으로 가지면 e를 1 증가시켜 다음 자식을 탐색..