문제 링크 https://www.acmicpc.net/problem/1644 1644번: 소수의 연속합 첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000) www.acmicpc.net 풀이 에라토스테네스의 체를 사용해 n 보다 작거나 같은 소수들을 구합니다. (line 2~ line 8) 소수를 담을 배열 prime을 선언합니다. 배열 a는 소수가 아닌 수를 지우기 위해 사용됩니다. 2 ~ n 범위의 수 중에서 소수를 채택하고, 그 소수의 배수는 모두 지우게 됩니다. 투 포인터를 이용해 연속된 수열(소수)의 부분합을 구합니다. (line 9 ~ line 19) left, right의 초기 인덱스를 0,0으로 설정합니다. 우측 포인터를 가리키는 right의 인덱스가 소수를 담은 배열 pr..
Koala - 5기
링크 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 풀이 과정 투포인터로 풀면 O(n)시간 안에 풀리는 문제이다. 다만 유의해야할점은 4 4 1 5 2 2 와 같은 예시에서 5지점에서 포인터가 역전될수도 있으므로 단순히 high>=low를 반복조건으로 두면 틀리게 된다. 따라서 포인터가 역전당했을때 다시 포인터를 옮겨주거나, 혹은 조건에서 high>=low를 제거하면 된다. 코드 #include usi..
https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 문제 풀이 첫번째 줄에는 전체 용액의 수를 입력으로 받고, 두번째 줄은 각 용액의 특성값을 받아 liq라는 리스트를 생성한다. liq의 값들은 정렬된 순서로 주어졌기 때문에 두 용액의 합이 0에 가까운 정도를 구하기 위해서 투 포인터를 이용한다. 가장 작은 값과 가장 큰 값부터 시작해서 점차 안쪽의 용액 특성값의 합을 구하는 방식으로, 이를 위해 p1은 liq의 앞부분에서, p2는 liq의 ..
문제 링크 문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다. 자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오. 첫째 줄에 자연수 N을 연속..
링크 https://www.acmicpc.net/problem/14465 14465번: 소가 길을 건너간 이유 5 첫 줄에 N, K, B (1 ≤ B,K ≤ N)가 주어진다. 그 다음 B줄에는 고장난 신호등의 번호가 하나씩 주어진다. www.acmicpc.net 풀이 과정 1 (실패) 처음 문제를 풀 때에는 벡터에 고장난 신호등의 리스트를 집어넣고, sort함수로 정렬해서 해당 신호등을 고쳤을 때 연속된 신호등의 개수가 K개 이상인지 확인하는 방식으로 문제를 풀었다. 하지만 그러다 보니 인덱싱의 문제도 있고, 무엇보다도 100%에서 계속해서 오답처리가 돼서 결국 방법을 바꿨다. 우선은 처음 했던 방식을 설명해 보겠다. cont: 연속된 신호등의 개수 num: 고쳐야 하는 신호등의 개수 min: 현재 가장..
문제 https://www.acmicpc.net/problem/15813 15813번: 너의 이름은 몇 점이니? 소윤이는 성필이에게 단단히 화가 났다. 성필이가 자꾸 소윤이의 이름을 놀리는 것이다! 극대노한 소윤이는 이름에 대해 많은 검색을 하던 도중 "이름점수"라는 것을 발견하게 된다. 이름 점수 www.acmicpc.net 코드 count = int(input()) name = list(input()) ascii_list = [] for i in name: ascii_list.append(ord(i)-64) print(sum(ascii_list)) 풀이 count는 입력을 받지만 실제로 사용하지는 않는다. 글자를 입력받아 글자 리스트로 바꿔준 후에, 아스키 코드로 A가 65임을 이용하여 모든 글자를 ..
링크 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 작년에 dp 공부를 처음하면서 풀지 못했다가 다시 도전해서 푼 문제이다. 최장 공통 부분 수열, 최장 공통 부분 문자열이 다른 것으로 알고 있는데 다음에는 예전에 심심해서 찾아보다가 발견한 최장 공통 부분 문자열 문제를 찾아서 풀어 볼 생각이다. 2차원 dp를 차례대로 채워가면서 s1[i] == s2[i]이면 d[i - 1][j - 1] + ..
https://www.acmicpc.net/problem/9226 9226번: 도깨비말 도깨비말은 언어 유희 중 하나로, 글자를 특정 법칙에 따라 재구성하는 것을 말한다. 영어권에서는 피그라틴어라는 것이 있다. 주로 어린이들이 많이 쓰는 데, 남들에게 무슨 말인지 모르게 하 www.acmicpc.net import sys while True: x=input() tex=list(x) if x=='#': sys.exit() fix=['a','e','i','o','u'] s=0 for i in tex: if i in fix: s=1 break if s==0: tex.extend('ay') b=''.join(tex) print(b) continue for i in range(len(tex)): if tex[0]..
BOJ 16236번 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net * 한 게시글에 코드 블록 언어를 하나로 통일해야 해서 Python 코드는 하이라이트가 정상적이지 않습니다ㅠ Intro 처음에는 물고기들의 위치를 저장한 뒤, 각 물고기의 위치에서 현재 상어 위치까지의 거리를 구해 우선순위에서 일 순위인 물고기를 사용하는 방식으로 구현하였습니다. 그랬더니 시간 초과가 계속해서 발생했습니다. 위 풀이 방식은 가장 가까우면서 우선순위에서 일순위인 물고기를 찾기 위해, BFS를 상어가 먹을 수 있는..
https://www.acmicpc.net/problem/15813 15813번: 너의 이름은 몇 점이니? 소윤이는 성필이에게 단단히 화가 났다. 성필이가 자꾸 소윤이의 이름을 놀리는 것이다! 극대노한 소윤이는 이름에 대해 많은 검색을 하던 도중 "이름점수"라는 것을 발견하게 된다. 이름 점수 www.acmicpc.net 문제분석 입력할 문자열의 길이를 먼저 입력한다. 다음으로 입력한 문자열의 길이만큼 대문자 알파벳들을 입력한다. 입력한 각 알파벳 대문자의 순서만큼 모두 합친 값이 문제에서 요구하는 이름의 점수를 뜻한다. 코드 문제풀이 우선, 문제에서 요구하는 문자열의 길이(n)와 문자열(a)을 입력받는다. 다음으로 문자열의 각각의 한 글자를 리스트처럼 취급하기 위해서 for문을 활용한다. 여기서 처음에..
https://www.acmicpc.net/problem/1874 1874번: 스택 수열 1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다. www.acmicpc.net 문제 코드 #include using namespace std; #include #define PI 3.141592653589793 #define ll long long int main(void) { ios_base::sync_with_stdio(0); cin.tie(0); stack s; string c; int ..
이 문제에서 주의해야 할 점은 player1이 이기다가.. 다시 비기게 되는 순간에 player1이 이기는 시간이 멈추어져야 하고, player2가 다시 선방(?)하게 될 때 또 player2의 이기는 순간이 시작되어야 한다. 그래서 이 때 관점을 우리가 하나씩 입력받는 순간마다 바뀌도록 했는데, 그 방법은 예를 들어 player 1 -> 1 -> 2 -> 2 -> 2 ->라고 하면 player가 이길 때는 +1로 양수로 한 칸 가고 2가 이길 때는 -1로 간다. 즉, 0이 되는 순간이 비기는 거고 양수는 player1이 이기는 거, 음수는 player2가 이기는 거다. (1, 2, 1, 0, -1 이 됨) 그렇게 하면 비기는 순간/player2가 이기는 순간이 헷갈리지 않게 잘 나타나졌다!! 그리고 이..
