문제 https://www.acmicpc.net/problem/2495문제여덟 자리의 양의 정수가 주어질 때, 그 안에서 연속하여 같은 숫자가 나오는 것이 없으면 1을 출력하고, 있으면 같은 숫자가 연속해서 나오는 구간 중 가장 긴 것의 길이를 출력하는 프로그램을 작성하라. 예를 들어 세 개의 숫자 12345123, 17772345, 22233331이 주어졌다고 하자. 12345123은 연속하여 같은 숫자가 나오는 것이 없으므로 1을 출력하고, 17772345는 7이 세 개 연속하여 나오므로 3을 출력하며, 22233331의 경우에는 2가 세 개, 3이 네 개 연속해서 나오므로 그 중 큰 값인 4를 출력하여야 한다. 입력첫째 줄부터 셋째 줄까지 각 줄에 하나씩 세 개의 여덟 자리 양의 정수가 주어진다...
분류 전체보기
https://www.acmicpc.net/problem/30648알고리즘한 좌표에 두송이의 꽃이 피어있게 되는 시간을 구하는 문제이다.우리가 기억해야 할것은 다음 꽃이 필 자리에 꽃이 존재하는가현재 꽃이 핀 위치와 다음에 꽃이 필 위치를 기억해주고, 반복문을 통해 시간을 구해주는 방식으로 코드를 구성하였다.해당 좌표에 꽃이 있는지 확인할 배열, 다음 꽃이 필 위치 좌표 변수를 통해 해당 위치에 꽃이 존재했다면 반복문을 종료하고 시간을 출력해주었다.해당 위치에 꽃이 존재하지 않았다면 다음 꽃이 필 좌표를 계산해주는데, x+y+2가 r보다 작으면 다음 꽃이 필 위치는 x+1, y+1이고x+y+2가 r보다 크면 다음 꽃이 필 위치는 x%2, y%2이고, 소수점은 버리므로 //로 정수형을 만들어준다.코드imp..
https://www.acmicpc.net/problem/2003문제N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.입력첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.출력첫째 줄에 경우의 수를 출력한다.코드def count_subarrays_with_sum(N, M, A): start, end = 0, 0 current_sum = 0..
https://www.acmicpc.net/problem/2842알고리즘 분류그래프 이론그래프 탐색이분 탐색너비 우선 탐색두 포인터문제상덕이는 언덕 위에 있는 마을의 우체국에 직업을 얻었다. 마을은 N×N 행렬로 나타낼 수 있다. 행렬로 나뉘어진 각 지역은 우체국은 'P', 집은 'K', 목초지는 '.' 중 하나로 나타낼 수 있다. 또, 각 지역의 고도도 알고 있다.매일 아침 상덕이는 마을의 모든 집에 우편을 배달해야 한다. 배달은 마을에 하나밖에 없는 우체국 'P'가 있는 곳에서 시작한다. 상덕이는 현재 있는 칸과 수평, 수직, 대각선으로 인접한 칸으로 이동할 수 있다. 마지막 편지를 배달하고 난 이후에는 다시 우체국으로 돌아와야 한다.상덕이는 이렇게 매일 아침 배달을 하는 것이 얼마나 힘든지 궁금해졌..
https://www.acmicpc.net/problem/14465입력첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다.출력정상적으로 작동하는 연속 K개의 신호등이 존재하려면 최소 몇 개의 신호등을 수리해야 하는지 출력한다. 코드n, k, b = map(int, input().split())arr = [0 for _ in range(n)]for _ in range(b): arr[int(input())-1] = 1 left = 0right = k-1tmp = sum(arr[0:k])ans = tmpwhile right 풀이 과정1. 고쳐야하는 고장난 신호등을 1로 표시2. K 간격만큼에서 고쳐야하는 신호등 수를 그 1들의 합으..
문제 https://www.acmicpc.net/problem/2018 Algorithm Codeimport sysinput = sys.stdin.readlineN = int(input())start = 1end = 1total = 1count = 1if N == 1 or N == 2: print(1) sys.exit()while end
접근 방법a 배열을 통해 초밥의 가짓수 d(2 ~ 3000)가 k개의 접시를 연속해서 먹을 때 있는지 확인먼저 반복문을 돌려서 0 ~ k-1 접시를 연속으로 먹었을 때 최댓값을 계산(윈도우로 활용)해당 윈도우를 접시를 지우고, 추가하며 연속된 접시를 k 개 먹었을 때, 최댓값을 계산(슬라이딩 윈도우) 코드#include #include using namespace std;int a[3001] = {0, };int main() { int N, d, k, c; cin >> N >> d >> k >> c; vector v(N); for (int i = 0; i > v[i]; int sol = 0, result = 0; for (int i = 0; i
문제 https://www.acmicpc.net/problem/1700 Algorithm그리디 알고리즘cntK_list 에 각 전기용품마다 사용 순서를 따로 deque로 저장한다.그리디하게 해결하기 위해,1. 멀티탭에 플러그가 꽂혀 있고, 해당 전기용품이 꽂혀있는지2. 그렇지않다면 멀티탭에 공간이 남아있는지3. 그렇지 않다면 멀티탭을 정렬한 후, 하나를 뽑는 후 새로 꽂는다. 이 때, 남은 전기용품의 순서를 기준으로 정렬한다. Codefrom collections import dequeinput = __import__('sys').stdin.readlineN, K = map(int, input().rstrip().split())K_list = deque(list(map(int, input().rst..
문제 https://www.acmicpc.net/problem/18111문제팀 레드시프트는 대회 준비를 하다가 지루해져서 샌드박스 게임인 ‘마인크래프트’를 켰다. 마인크래프트는 1 × 1 × 1(세로, 가로, 높이) 크기의 블록들로 이루어진 3차원 세계에서 자유롭게 땅을 파거나 집을 지을 수 있는 게임이다.목재를 충분히 모은 lvalue는 집을 짓기로 하였다. 하지만 고르지 않은 땅에는 집을 지을 수 없기 때문에 땅의 높이를 모두 동일하게 만드는 ‘땅 고르기’ 작업을 해야 한다.lvalue는 세로 N, 가로 M 크기의 집터를 골랐다. 집터 맨 왼쪽 위의 좌표는 (0, 0)이다. 우리의 목적은 이 집터 내의 땅의 높이를 일정하게 바꾸는 것이다. 우리는 다음과 같은 두 종류의 작업을 할 수 있다.좌표 (i,..
https://www.acmicpc.net/problem/8958알고리즘연속된 기호, 숫자를 세는 조건은 무엇일까? 또한 지금까지 연속된 기호, 수가 몇개인지 세기 위해선 어떻게 해야 할까?많은 방법이 있겠지만 이 문제에서는 이번 기호가 'O'라면, 분기를 나누어 '이전 기호'가 'X' 라면 연속된 횟수 1로 바꾸거나,그게 아니라면 계속해서 연속 횟수 c를 하나 증가시키는 방법을 사용했다. 그 이외의 경우라면, 현재 기호가 'X'이므로 c를 0으로 초기화했다. 점수를 계산하기 위해선 '현재까지의 O 수'를 세어야 하는데 이 역할을 cnt로 대신했다. 또한 이전 원소를 체크하기 때문에 index가 0번째인 원소는 c를 1로 고정하도록 예외 처리 해 주었다.코드input = __import__('sys')...
문제 https://www.acmicpc.net/problem/1890 Algorithm1. 처음엔 재귀함수를 사용해서 백트래킹으로 완전탐색을 시도했는데 시간 초과가 발생했다.2. DP를 사용하여 각 타일에 올 수 있는 경우의 수만 체크하여 각 타일에 갈때마다 dp 이중 배열의 값을 더해줬다. Codeimport java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.StringTokenizer;public class Main { private static Buff..
https://www.acmicpc.net/problem/1965알고리즘 앞에 있는 상자의 크기가 뒤에 있는 상자의 크기보다 작으면, 앞에 있는 상자를 뒤에 있는 상자에 넣을 수 있고, 한 번에 넣을 수 잇는 최대의 상자 개수를 찾는 코드를 구성해야 하므로, 해당 수열에서 가장 길이가 긴 증가하는 수열을 찾으면 된다. dp배열을 만들고, i번째 원소보다 앞에 있는 원소(0 ~ i-1)들중에 i번째 원소보다 작은 원소의 개수를 카운팅해주어 dp배열에 저장하는 방식으로 구성하였다.https://www.acmicpc.net/problem/11053해당 문제와 코드가 유사하다.코드import sysinput = sys.stdin.readlinen = int(input())arr = list(map(int,inp..
