연잎의 develog

19585번: 전설 (acmicpc.net) 19585번: 전설 Sogang ICPC Team에는 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수 www.acmicpc.net [문제] 색상 이름과 닉네임의 순서로 이여서 팀명을 지으면 ICPC 리저널에서 수상할 수 있다는 전설이 있다. 색상 이름들과 닉네임들이 주어질 때, Q개의 팀에 대해 다음 리저널에서 수상할 수 있을지 전설에 기반해 알려주는 프로그램을 작성하자. [해결전략] (1 ≤ C, N ≤ 4,000)이므로 만들 수 있는 모든 경우의 수 4000 * 4000 을 set에 저장시켜도 된다. 입력한 팀명이 존재하는지 이진..

19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 (acmicpc.net) 19582번: 200년간 폐관수련했더니 PS 최강자가 된 건에 대하여 2220년에도 “2220 신촌지역 대학생 프로그래밍 대회 동아리 연합 수시 대회”가 성공적으로 개최된다. SUAPC은 이제 모든 학생이 즐길 수 있도록 다양한 난이도의 대회가 1년에 수시로 열리며, www.acmicpc.net [문제] 각 대회마다 참가자격이 생겨 모든 대회에 참가하지 못할 수도 있다! 상금의 독식을 막기 위해 대회마다 “상금 상한”이 존재하며, 어떤 대회를 참가하기 전까지 모은 상금의 합이 그 대회의 상금 상한을 초과한다면 그 대회는 참가할 수 없다. 대회가 열리는 순서는 정해져 있고 대회들의 시간은 겹치지 않는다. 올해 열..

19575번: Polynomial (acmicpc.net) 19575번: Polynomial 경근이는 수학을 좋아한다. 수학을 너무 좋아하는 나머지 다항식을 빠르게 평가하는 프로그램을 작성했다. 미지수 x로 구성된 다항식 f(x)에서 x에 k를 대입하여 f(k)를 구하는 것을 평가라고 한다 www.acmicpc.net [문제] [해결전략] [풀이] #include #include using namespace std; const int MOD = 1e9 + 7; int solve(int n,int x, vector coef) { long long ans = coef[0] ; for (int i = 1; i > n>> x; vector coef(n+1, 0); int degree; for (int i = 0..

19572번: 가뭄(Small) (acmicpc.net) 19572번: 가뭄(Small) 3개의 양의 정수가 입력으로 들어온다. 각각은 d1, d2, d3을 의미한다. (1 ≤ d1, d2, d3 ≤ 106) www.acmicpc.net [문제] [해결전략] 입력값을 각각 d1,d2,d3 라고 한다면 a+b+c = d1+d2+d3 즉, 아래 세개의 식으로 구성된 삼차 연립방정식을 풀어주면 된다! a+b = d1 ...(1) a+c = d2 ...(2) b+c = d3 ...(3) (1) - (2) = b - c = d1-d2 ...(4) (3) + (4) =2b = d3+d1-d2 b = (d3+d1-d2)/2 c= d3 - b a = d1 - b 만일 구한 a,b,c 값이 음수가 된다면 답을 구할 수 ..

19583번: 싸이버개강총회 (acmicpc.net) 19583번: 싸이버개강총회 첫번째 줄에는 개강총회를 시작한 시간 S, 개강총회를 끝낸 시간 E, 개강총회 스트리밍을 끝낸 시간 Q가 주어진다. (00:00 ≤ S < E < Q ≤ 23:59) 각 시간은 HH:MM의 형식으로 주어진다. 두번째 줄부터는 www.acmicpc.net [문제] 다음과 같이 출석부를 관리하기로 결심했다. 1.개강총회를 시작하기 전에, 학회원의 입장 확인 여부를 확인한다. 학회원의 입장 여부는 개강총회가 시작한 시간 이전에 대화를 한 적이 있는 학회원의 닉네임을 보고 체크한다. 개강총회를 시작하자마자 채팅 기록을 남긴 학회원도 제 시간에 입장이 확인된 것으로 간주한다. 2. 개강총회를 끝내고 나서, 스트리밍을 끝낼 때까지 학..

3190번: 뱀 (acmicpc.net) 3190번: 뱀 'Dummy' 라는 도스게임이 있다. 이 게임에는 뱀이 나와서 기어다니는데, 사과를 먹으면 뱀 길이가 늘어난다. 뱀이 이리저리 기어다니다가 벽 또는 자기자신의 몸과 부딪히면 게임이 끝난다. 게임 www.acmicpc.net [문제] [해결전략] 우선 뱀과 사과의 위치를 저장해둘 2차원 배열이 필요하다. 뱀을 1로 저장하고, 사과를 2로 저장하자. 1 1 0 0 0 1 2 0 0 2 0 0 0 0 0 0 위 예시에서 뱀의 크기는 3이고 사과는 (3,2) , (2,3) 에 위치해있다. 또한 뱀의 이동 좌표를 *덱(deque), 위치변환정보를 *큐(queue)에 저장한다. *뱀의 이동좌표를 덱에 저장시키는 이유는 머리를 다음칸에 위치시키고 조건에 따라서..

2011번: 암호코드 (acmicpc.net) 2011번: 암호코드 나올 수 있는 해석의 가짓수를 구하시오. 정답이 매우 클 수 있으므로, 1000000으로 나눈 나머지를 출력한다. 암호가 잘못되어 암호를 해석할 수 없는 경우에는 0을 출력한다. www.acmicpc.net [문제] [해결전략] 예전에 알튜비튜에서 과제로 나왔던 문젠데 dp라길래 패스했던 문제 ^^.. 다시 한번 풀어보려고 하는데 쉽지 않다. dp문제만 나오면 머리가 맹해진다. 그래서 알튜비튜 레포지토리에 있는 풀이 참고해서 해독하면서 풀었다.. dp[i]에 i번째 글자까지 해석했을때 나올 수 있는 경우의 수를 저장할것이다. 1. 한자리수로 해석하는경우 dp[i] += dp[i-1] 2. 두자리수로 해석하는경우 dp[i] += dp[i-..

2210번: 숫자판 점프 (acmicpc.net) 2210번: 숫자판 점프 111111, 111112, 111121, 111211, 111212, 112111, 112121, 121111, 121112, 121211, 121212, 211111, 211121, 212111, 212121 이 가능한 경우들이다. www.acmicpc.net [문제] [해결전략] 1. 재귀 + 브루트 포스로 각 점에서 시작하여 만들 수 있는 모든 경우의 수를 다 해본다. 2. 재귀 함수의 인자로 cnt: 이동횟수 를 넘겨주어 5번의 이동횟수를 다 채우면 set에 추가시킨다. 3. 모든 연산을 완료한 뒤에 set에 들어있는 원소의 개수가 가능한 경우의 수 들이다! set 컨테이너를 사용하는 이유는 중복을 방지하고 경우의수를 c..

20937번: 떡국 (acmicpc.net) 20937번: 떡국 Naver D2를 아시나요? D2는 For Developers, By Developers의 약자로, 개발자들을 위해 개발자들이 직접 만들어 가고 있는 네이버 개발자 지원 프로그램입니다. 네이버가 축적한 기술과 지식을 공유하고, 외 www.acmicpc.net [문제] 떡국 그릇 위에는 크기가 더 작은 떡국 그릇만을 쌓을 수 있다. 떡국 그릇들의 크기가 주어졌을 때, 떡국 그릇 탑의 최소 개수를 구하라. [해결전략] 떡국탑의 개수를 최소로 하려면 하나의 탑에 최대한 많은 떡국 그릇을 올려쌓아야한다. 하나의 떡국 탑에는 최대로 서로다른 n개의 떡국그릇이 위치할 수 있다. 그런데 크기가 같은 경우, 하나의 떡국 그릇 탑에 속할 수 없다 따라서 크..

20944번: 팰린드롬 척화비 (acmicpc.net) 20944번: 팰린드롬 척화비 흥선이는 팰린드롬을 싫어한다. 어느 날 지구를 정복한 흥선이는 팰린드롬 척화비를 세워, 전 지구의 팰린드롬을 없애버렸다. 그리고 수미상관 순수비를 만들어 수미상관을 널리 퍼뜨렸다. 팰 www.acmicpc.net [문제] [해결전략] 문자열의 길이 n이 주어지고 1. 펠린드롬 2. 수미상관 조건을 모두 만족하는 문자열 중 하나를 출력해야한다. 사실 단순히 생각했을때에는 뒤집어읽을때에도 같으면서 앞쪽 절반과 뒤쪽 절반이 같은 문자열을 찾는다는 것은 불가능해보인다. 펠린드롬 (뒤집어 읽을때 같다) 은 다음과 같은 구조를 취하는데 🟥🟨🟦 🟦🟨🟥 수미상관 (뒤집어 읽을때 같다) 은 다음과 같은 구조를 취하기때문이다. 🟥🟨🟦 🟥..