https://www.acmicpc.net/problem/20922 20922번: 겹치는 건 싫어홍대병에 걸린 도현이는 겹치는 것을 매우 싫어한다. 특히 수열에서 같은 원소가 여러 개 들어 있는 수열을 싫어한다. 도현이를 위해 같은 원소가 $K$개 이하로 들어 있는 최장 연속 부분 수열www.acmicpc.net문제조건같은 원소 k개 이하최장 연속 부분 수열의 길이처음보는 문제유형이라 많이 당황했다,,dp, LCS 등등 알고리즘을 고민해봤지만, 도저히 풀리는 그림이 나오지 않았다.따라서 투 포인터라는 접근방식이 필요했다. https://khu98.tistory.com/187 [백준OJ] 20922번 겹치는 건 싫어https://www.acmicpc.net/problem/20922 20922번: 겹치는 건..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 문제조건 목표지점부터 모든 지점에 대해서 목표지점까지의 거리 구하기 너무 당연하게 BFS로 풀이를 시작했다. #include #include using namespace std; int n, m, map[1001][1001], visited[1001][1001], dist[1001][1001]; int dy[] = { -1, 0, 1, 0 }; int ..

https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩 www.acmicpc.net 문제조건 몸무게 : x, 키 : y → (x, y) x, y 둘다 커야 덩치가 더 크다고 한다. 각 사람의 덩치 등수를 매긴다 이 문제는 진짜 너무 쉽다,,,, 그냥 완전 탐색 문제였다. 한명씩 전부 비교해보면서 각각 등수를 출력하기만 하면된다,,! #include #include int n; using namespace std; vector v; int main(){ cin >> n..

https://www.acmicpc.net/problem/8979 8979번: 올림픽 입력의 첫 줄은 국가의 수 N(1 ≤ N ≤ 1,000)과 등수를 알고 싶은 국가 K(1 ≤ K ≤ N)가 빈칸을 사이에 두고 주어진다. 각 국가는 1부터 N 사이의 정수로 표현된다. 이후 N개의 각 줄에는 차례대로 각 www.acmicpc.net 문제를 보자마자 딱 느꼈다. 쉬운 문젠데 if문 잘 걸어 줘야겠다,,,, 특정 나라의 순위를 구하는 거여서 그냥 배열로 전부 나타내 주었다. #include #include #include using namespace std; int gold[1001], silver[1001], bronze[1001]; int n, k; int main() { cin >> n >> k; fo..

https://www.acmicpc.net/problem/1415 1415번: 사탕 첫째 줄에 슈퍼에 있는 사탕의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 사탕의 가격이 주어진다. 사탕의 가격은 10,000보다 작거나 같은 음이 아닌 정수 www.acmicpc.net 문제조건 사탕의 개수 : n개 사탕 가격의 합이 소수 모양이 똑같은 방법은 사지 않는다. 제일 먼저 떠오른 생각은 집합이었다. 집합이 한번 나오면 모양이 똑같은 방법을 커버할 수 있고, 그 집합의 원소들의 합이 소수가 되면 되기 때문이다. 라고 생각했지만 도저히 이 방법으로는 풀리지 않을 것 같았다,,, 일단 로직에 대해서는 더 고민해보기로 하고 소수 구하는 알고리즘을 보겠다. void isP..

https://www.acmicpc.net/problem/10431 10431번: 줄세우기 초등학교 선생님 강산이는 아이들을 데리고 단체로 어떤 일을 할 때 불편함이 없도록 새로 반에 배정받은 아이들에게 키 순서대로 번호를 부여한다. 번호를 부여할 땐 키가 가장 작은 아이가 1 www.acmicpc.net 자기 앞에 자기보다 키가 큰 학생이 없다면 그냥 그 자리에 서고 차례가 끝난다. 자기 앞에 자기보다 키가 큰 학생이 한 명 이상 있다면 그중 가장 앞에 있는 학생(A)의 바로 앞에 선다. 이때, A부터 그 뒤의 모든 학생들은 공간을 만들기 위해 한 발씩 뒤로 물러서게 된다. 학생들이 뒤로 물러 난 걸음 수? 처음에는 정렬이 안될때마다 학생을 직접 집어넣어줘야하는줄 알고 까다롭다고 생각했다. 근데 조금만..

https://www.acmicpc.net/problem/9655 9655번: 돌 게임 상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다. www.acmicpc.net 뭔가 정형적인 알고리즘으로 접근이 되지 않아서 직접 예시를 들어가며 풀어봤다. 돌 개수 이기는 사람 1 상근 2 창영 3 상근 4 창영 5 상근 규칙이 나왔다. 어차피 한번에 가져갈 수 있는 수는 1,3개로 제한되므로, 돌의 개수기 홀수일땐 상근이 이기고, 짝수일땐 창영이 이긴다. #include using namespace std; int n; //1 or 3 개씩 가져갈 수 있음 int main(){ cin >> n; if (n % 2) cout

https://www.acmicpc.net/problem/1157 1157번: 단어 공부 알파벳 대소문자로 된 단어가 주어지면, 이 단어에서 가장 많이 사용된 알파벳이 무엇인지 알아내는 프로그램을 작성하시오. 단, 대문자와 소문자를 구분하지 않는다. www.acmicpc.net 가장 많이 쓴 영어 단어를 대문자로 출력하라. 사실 그냥 문자를 숫자로 취급한 아스키코드로 쉽게 풀어줄 수도 있지만, 저번에 map으로 이런 비슷한 문제를 풀어 봤던것 같아서 map을 써서 풀어 볼 것이다. key-value로 char-int로 두면 각 문자가 등장한 횟수를 쉽게 알 수 있다. #include #include using namespace std; string s; map m; //가장 많이 사용된 알파벳 2개이상일..

https://www.acmicpc.net/problem/2292 2292번: 벌집 위의 그림과 같이 육각형으로 이루어진 벌집이 있다. 그림에서 보는 바와 같이 중앙의 방 1부터 시작해서 이웃하는 방에 돌아가면서 1씩 증가하는 번호를 주소로 매길 수 있다. 숫자 N이 주어졌 www.acmicpc.net 1번방 부터 n번방 까지의 최소거리를 구하는 문제이다. 접근방법은 규칙파악이었다. 뭔가 육각형으로 쭉 둘러쌓여있으니까, 숫자 6과 관련된 규칙이지 않을까 생각했다. 1부터 시작해서 맨바깥테두리를 한번씩 채울때 마다 몇개의 육각형이 있는지 세어 봤다. 1, 6, 2*6, 3*6, 4*6 ... 순이다. 점화식을 세워보면 6^k (k >=0 인 정수) 로 나타 낼수 있다. 뭔가 다 파악해놓고 1시간가량 머리가..

https://www.acmicpc.net/problem/5073 5073번: 삼각형과 세 변 각 입력에 맞는 결과 (Equilateral, Isosceles, Scalene, Invalid) 를 출력하시오. www.acmicpc.net 수학을 한지 꽤 오래되어서 삼각형의 조건을 만족하지 못하는 경우,,,? 를 몰라서 엄청 당황했다. 두변의 길이의 합이 나머지 한변의 길이보다 커야 삼각형이 된다. 나 중학교 나왔는데,,, 조건이 너무 많아서 구현하는데 헷갈렸다. 그리고 이 문제는 if문과 else-if문이 어디서 걸리는지 잘 판단 해야 한다. 아니면 while문 안에서 무한루프등에 빠질 수 있으니,, 특히 종료조건으로 if문은 따로! 빼줘야한다 #include using namespace std; int..