순간을 성실히, 화려함보단 꾸준함을

www.acmicpc.net/problem/4781 4781번: 사탕 가게 각 테스트 케이스의 첫째 줄에는 가게에 있는 사탕 종류의 수 n과 상근이가 가지고 있는 돈의 양 m이 주어진다. (1 ≤ n ≤ 5,000, 0.01 ≤ m ≤ 100.00) m은 항상 소수점 둘째자리까지 주어진다. 다음 n개 www.acmicpc.net 문제 : n종류의 사탕을 가지고 있고 m 원을 가지고 있을때 사탕을 가질 수 있는 최대무게를 구하여라 해설 : 처음에 보고 그냥 냅색 문제구나 했지만,,,냅색문제와 가장 큰 차이점이 존재합니다. 바로 '갯수'입니다. 차근 차근 접근해 보면 일단 가장 단순하게 모든 경우의 수를 구하는 방법은 당연히 시간초과가 발생합니다. 그럼 우린 냅색문제를 푼 것처럼 접근해 봅시다. dp[i][..

www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 문제 : "문제가 넘나 복잡하여 그냥 생략하겠습니다. 디스크립션 꼼꼼하게 읽으세요" 해설 : 2021 상반기 삼성 문제입니다. 전형적인 빡구현 문제인데 솔직히 삼성문제 치고 굉장히 쉽게 나온 문제인 것 같습니다. 만약 실제 시험장에서 치셨더라면 아무리 못해도 1시간 안에 클리어 해주셔야지 2번째 문제로 무난하게 넘어갈 것 같네요. (화이팅 입니다 모두들!!!!!힘냅시다) 먼저 주어진 조건들을 정리해 봅시..

www.acmicpc.net/problem/13702 13702번: 이상한 술집 프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용 www.acmicpc.net 문제 : n개의 주전자가 주어지고 k 명에게 최대한 많은 양의 술을 나누어 주고 싶습니다. 해설 : 이분탐색 문제입니다. 다만 주의할 점은 최대값이 될 조건들을 잘 생각해서 걸러내야됩니다. int 형 범위를 넘어 갈 수 있어서 long long 형으로 선언해 주세요 #include using namespace std; using ll = long long; ll arr[10000]; int main() { int..

www.acmicpc.net/problem/4095 4095번: 최대 정사각형 입력은 여러 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 N과 M이 주어진다. (1 ≤ N,M ≤ 1,000) 다음 N개의 줄에는 공백으로 구분된 M개의 수가 주어진다. 마지막 줄에는 0이 두 www.acmicpc.net 문제 : 격자판이 주어지고 1로만 이루어진 정사각형의 최대 너비 혹은 높이를 구하시오 해설 : DP문제입니다. 먼저 정사각형이 될 수 있는 조건부터 생각해 보면 모든 길이가 동일시 되야죠. 그러면 현재 내가 위치한 칸을 기준으로 위쪽 왼쪽 대각선 방향으로 전부 동일하다면? 정사각형이 될 수 있습니다. 이 중 공통된 길이를 택해야 되니 3가지 방향중 최소길이를 택한 후 +1 을 해주면 됩니다..

www.acmicpc.net/problem/17143 17143번: 낚시왕 낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. www.acmicpc.net 문제 : 낚시왕은 한칸씩 오른쪽으로 움직이고 그 열에 해당하는 가장 가까운 상어를 잡습니다. 이때 상어는 속력과 방향,크기를 가지고 있고 만약 같은 칸에 동일한 상어가 2마리 이상 겹친다면 크기가 가장 큰 상어가 전부 잡아먹습니다. 이때 낚시왕이 낚시를 끝내고 잡은 상어들의 무게의 합을 구하시오 해설 : 전형적인 삼성 문제라 너무 힘드네요 ㅠㅠㅠㅠㅠㅠㅠ 구현력이 대체 언제 느련지.... 가장..

www.acmicpc.net/problem/3793 3793번: Common Subsequence A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = another sequence Z = is a subsequence of X if there exists a strictly increasing sequence > x >> y; if (cin.eof()==true)break; memset(dp, 0, sizeof(dp)); solve(); } } void solve() { for (int i = 0; i < x.length(); i++) { ..

www.acmicpc.net/problem/2418 2418번: 단어 격자 첫째 줄에 3개의 수 H, W, L이 주어진다. H는 격자의 높이, W는 격자의 격자의 너비, L은 단어의 길이이다. (1 w >> l; for (int i = 0; i > str[i]; cin >> s; memset(dp, -1, sizeof(dp)); ll ans = 0; for (int i = 0; i = w)continue; if(str[tx][ty]==s[step+1]) ret+=dfs(tx, ty, step ..

www.acmicpc.net/problem/14678 14678번: 어그로 끌린 영선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 정점의 개수 N이 주어진다. (1 ≤ N ≤ 1,000,000) 두 번째 줄부터 N-1개의 줄에 정점 a와 정점 b가 주어진다. (1 ≤ a, b ≤ N) 정점 a와 정점 b www.acmicpc.net 문제 : 트리가 주어지고 영선이는 아무 정점에서 '왼발'부터 시작합니다. 이때 다른 한쪽발을 번가라가면서 한칸씩 이동할 수 있고 더이상 갈 곳이 없을때 '왼발'을 디딤고 있으면 영선이가 이깁니다. 영선이가 이길 수 있는 경우의 수를 구하시오 해설 : 단순히 모든 정점에서 DFS를 실행하여 나오는 경우의 수를 전부 구하면 되지 않냐? 라고 생각할 수도 있지만 정점..

www.acmicpc.net/problem/3360 3360번: 깡총깡총 CTP마을에 사는 토끼 아람이는 3,2,1미터씩 뛰어서 n미터를 지난다. 람토끼가 지나야하야 하는 길이가 주어졌을 때 점프 길이가 증가하지 않는 순서로 지나가는 방법은 총 몇 가지가 있을까? 찾 www.acmicpc.net 문제 : 3,2,1 칸 만큼만 점프가 가능하고 N을 만들려고 하는데 '증가하지 않는 수열' 형태로 만들 수 있는 경우의 수를 구하시오 해설 : 흠....전 어려웠습니다 ㅠㅠㅠ 단순 dp로 접근하려고 하면 절대 안되죠 10이 맥시멈이니깐 일단 '증가하지 않는 수열'의 의미를 생각해 보면 3x + 2y +z = N 의 형태로 식을 세울 수 있습니다. 여기서 z는 굳이 신경을 써줄 필요가 없죠. 1의 집합이니까요 그럼..

www.acmicpc.net/problem/18222 18222번: 투에-모스 문자열 0과 1로 이루어진 길이가 무한한 문자열 X가 있다. 이 문자열은 다음과 같은 과정으로 만들어진다. X는 맨 처음에 "0"으로 시작한다. X에서 0을 1로, 1을 0으로 뒤바꾼 문자열 X'을 만든다. X의 뒤에 www.acmicpc.net 문제 : 제일 처음 0이 주어지고 그다음 뒤집어서 붙여줍니다. 그럼 01이 되겠죠. 이걸 또다시 뒤집어서 붙여줍니다. 그럼 0110이 됩니다. 이것을 반복해서 긴 문자열을 만든다고 합시다. 이때 k 번째에 해당하는 문자를 구하시오. 해설 : 먼저 일정한 규칙을 알 수 있습니다. k번째에 해당하는 문자를 구하기 위해선 k 번째가 해당하는 문자열의 길이를 구해야 하는데 이건 2의 거듭제곱..

www.acmicpc.net/problem/7913 7913번: Afternoon Tea During his visit at Bytic Islands Byteasar really enjoyed the national beverage of Byteans, that is, tea with milk. This drink is always prepared in a strictly determined manner, which is as follows. Firstly the teacup is filled with tea mixed half and hal www.acmicpc.net 문제 : 처음 찻잔에 우유 절반과 차 절반이 들어있습니다. 우린 엄격한 규칙에 의해 이 차를 마실 수 있는데 규칙은 이렇습니다. 1. ..

programmers.co.kr/learn/courses/30/lessons/72411 코딩테스트 연습 - 메뉴 리뉴얼 레스토랑을 운영하던 스카피는 코로나19로 인한 불경기를 극복하고자 메뉴를 새로 구성하려고 고민하고 있습니다. 기존에는 단품으로만 제공하던 메뉴를 조합해서 코스요리 형태로 재구성해서 programmers.co.kr 문제,해설 : 문제를 단지 복붙이 아닌 설명을 하겠습니다. 먼저 각 사람들이 주문한 orders 배열이 주어집니다. 그리고 각 단품 메뉴들의 개수가 담겨진 배열들이 주어집니다. 이게 대체 무슨 말인지를 전 전혀~~~~~~~~~~~~~이해 못했었어요.(핵빡대가리세요?라고 말해도 안억울 합니다) 왜냐면 한글인데도 대체 무슨 말을 하는건지 못알아먹었거든요;;;; 천천히 해설을 해보면..