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

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 배열이 주어집니다. 그리고 각 단품 메뉴들의 개수가 담겨진 배열들이 주어집니다. 이게 대체 무슨 말인지를 전 전혀~~~~~~~~~~~~~이해 못했었어요.(핵빡대가리세요?라고 말해도 안억울 합니다) 왜냐면 한글인데도 대체 무슨 말을 하는건지 못알아먹었거든요;;;; 천천히 해설을 해보면..

www.acmicpc.net/problem/14677 14677번: 병약한 윤호 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 약을 먹어야 하는 날짜인 N이 주어진다. (1 ≤ N ≤ 500) 두 번째 줄에는 3N개의 약의 상태가 주어지는데, 아침 약은 B, 점심 약은 L, 저녁 www.acmicpc.net 문제 : 윤호는 알약을 먹습니다. B->L->D 순으로 먹습니다. 이때 최대로 먹을 수 있는 알약의 개수를 구하시오 해설 : 이 문제도 지난 포스팅한 문제와 크게 다를 바 없는 문제입니다. 왼쪽에서 선택하던 오른쪽에서 선택하던 어떤 선택을 하던지 간에 정답의 후보군이 될 수 있는 케이스들의 상태가 변하게 되고 우린 이를 BFS로 탐색해서 답을 찾을 수 있겠죠. 그럼 왼쪽,오른쪽 둘 중 어..

www.acmicpc.net/problem/3257 3257번: 발코딩 첫째 줄에 각 알파벳을 누가 입력했는지를 1 또는 2로 출력한다. 즉, 1로 표시한 위치의 알파벳만 읽으면 창영이가 생각한 단어, 2로 표시한 위치만 읽으면 강산이가 생각한 단어와 같아야 한다. www.acmicpc.net 문제 : 창영이과 강산이가 생각한 단어를 입력하고, 이 알파벳들을 서로 번가라가면서 입력하여 새로운 문자열을 만듭니다. 이때 창영이가 입력한건 1, 강산이가 입력한건 2 일때 새로운 문자열을 누가 입력했는지 출력하세요. 다수의 답 중 하나만 출력하면 됩니다. 해설 : 이런 문제에 정말 취약합니다. 문제를 보면 어떻게 '모델링'해야되는지 보이지가 않습니다. 현재 선택을 했을때 만들어질 수 있는 답의 케이스가 달라지고..

www.acmicpc.net/problem/17396 17396번: 백도어 첫 번째 줄에 분기점의 수와 분기점들을 잇는 길의 수를 의미하는 두 자연수 N과 M이 공백으로 구분되어 주어진다.(1 ≤ N ≤ 100,000, 1 ≤ M ≤ 300,000) 두 번째 줄에 각 분기점이 적의 시야에 보이는 www.acmicpc.net 문제 : 방문할 수 없는 정점들과 방문할 수 있는 정점들이 주어지고 0번 정점부터 n-1번 정점까지 최단거리를 구하시오 해설 : 평범한 다익스트라 문제입니다. 다만 방문 할 수 없는 정점을 뽑았을때는 그냥 무시해주면 되겠죠. 요새 자바 공부를 하고 있어서 자바로 한번 풀어봤는데 문법적인 요소가 꽤 까다로워서 싫네요;;; import java.io.*; import java.util.*..