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

https://www.acmicpc.net/problem/22942 22942번: 데이터 체커 데이터가 조건에 맞는다면 YES, 조건에 만족하지 않는다면 NO를 출력한다. www.acmicpc.net 해설 : 이 문제 꽤 재밌었습니다. 먼저 원의 교점이 없어야 합니다. 이때 중요한 포인트는 원의 x 좌표만 다를뿐 y 좌표는 동일하다는 것이죠. 즉, 굳이 원으로 표현해줄 필요없이 일직선으로 표현해 줄 수 있다는 것 입니다. 입력이 5 4 3 1 6 1 이런식으로 들어왔다고 하면 그림과 같이 표현해 줄 수 있겠죠. 그러면 NO 가 될 조건은???한 일직선이 다른 일직선 사이에 '걸쳐있으면' 됩니다. 이렇게 말이죠. 이는 스택을 사용해서 걸러주면 되겠죠? //package com.boj.practice; im..

https://www.acmicpc.net/problem/7573 7573번: 고기잡이 한국인의 식단에서 생선은 매우 중요한 단백질 공급원이다. 반면, 지구 온난화로 인한 바닷물의 온도 상승, 그리고 지금까지 마구잡이로 물고기를 잡은 결과로 점점 우리나라의 바다에서 물고 www.acmicpc.net 해설 : 단순히 생각했을때 2차원배열로 선언해서 접근할수도 있을 것 같지만 N의 범위가 1만이니 아마 메모리 초과가 발생할 것 입니다. 그런데 굳이 2차원 배열을 만들필요가 있을까요???그물의 길이도 100, 물고기의 최대 수도 100이니 그냥 주어진 입력값들만으로도 충분히 범위를 구할 수 있습니다. 즉, 모든 가능한 경우의 수를 직접 해보면 된다는 뜻입니다. 이때, 네방향(왼쪽 위, 오른쪽 위, 왼쪽 아래,..

https://www.acmicpc.net/problem/1301 1301번: 비즈 공예 첫째 줄에 다솜이가 가지고 있는 구슬의 종류 N이 주어진다. N은 3보다 크거나 같고, 5보다 작거나 같다. 둘째 줄부터 N개의 줄에 각각의 구슬이 총 몇 개 있는 지주어진다. 첫째 줄에는 1번 구슬, www.acmicpc.net 해설 : 사실 이런 문제를 보면 dp를 사용해야되는 건 알겠는데 점화식을 세우기가 바로 보이지는 않더라구요....그래서 항상 우리는 조건을 잘 보도록 합시다. N이 비정상적으로 범위가 작고 구슬의 총 개수도 35를 넘지는 않죠? 처음에는 브루트포스로 해도 되겠다 싶었는데 2^35은 감당이 안될 것 같아 패스했습니다. 점화식을 어떻게 세우면 좋을까요? 목걸이가 완성될 수 있는 조건을 확인하려..

https://www.acmicpc.net/problem/22236 22236번: 가희와 비행기 가희는 김포 공항에서 김해 공항까지 비행기를 타고 가려고 합니다. 비행기가 수평 방향으로 1만큼 이동하였을 때, 비행기의 고도는 1만큼 변화합니다. (상승 또는 하강) 비행기가 상승하거나 www.acmicpc.net 해설 : d 의 제한이 4000이 MAX이니 그냥 2차원 배열 넉넉하게 선언해주면 됩니다. 파스칼의 삼각형 문제 처럼 대각선에서 값들을 가져와 저장해 주면 됩니다. 이때, 조심할 점은 오버플로,,,,,,,,,조심합니다. 모듈러 연산을 해준다고 해도 덧셈 연산을 진행할때 int 형의 범위를 벗어나는 경우가 생길 수도 있습니다. #include using namespace std; using ll =..

https://www.acmicpc.net/problem/22234 22234번: 가희와 은행 가희는 창구가 하나인 은행을 운영하고 있습니다. 가희의 은행이 영업을 시작했을 때, 대기 줄에는 손님이 N명 있습니다. [그림 1] 카운터 직원과 N명의 손님 x번 손님에 대한 정보는 x번 손님의 www.acmicpc.net 해설 : 시뮬레이션 문제인데. 이런 문제는 큐를 사용하는 것보단 조건(Order) 와 같은 걸 추가해서 priority_queue로 해결하는 것이 훨씬 빠르고 유리하게 해결할 수 있는 것 같습니다. #include using namespace std; struct info { int p, t, c,order; bool operator cur.order; return c > cur.c; } ..

https://www.acmicpc.net/problem/22232 22232번: 가희와 파일 탐색기 첫 번째 줄에 jo_test 폴더에 있는 파일 개수 N과 가희가 설치한 OS에서 인식하는 파일 확장자의 개수 M이 공백으로 구분되어 주어집니다. 2번째 줄부터 N+1번째 줄까지 FILENAME.EXTENSION 형식의 문자열 www.acmicpc.net 해설 : 문제는 그냥 되게 간단한데 ㅋㅋㅋㅋㅋ 한가지 조건이라도 놓쳐버리면 고생할 문제네요. 연산자 오버로딩만 잘 어떻게 처리해주면 쉬운 문제입니다. 전 확장자가 둘다 붙거나, 둘다 붙지 않으면 3번째 조건으로 넘어가야 되는데 둘다 붙은 경우에만 생각해서 좀 해맸습니다. 연산자 오버로딩은 자유자재로 구현할 줄 알아야겠죵? #include using nam..

https://www.acmicpc.net/problem/22233 22233번: 가희와 키워드 1번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, floyd, os가 됩니다. 2번째 글을 쓰고 난 후에, 메모장에 있는 키워드는 set, os가 됩니다. map은 1번째 글과 2번째 글에 중복으로 등장하였음을 www.acmicpc.net 해설 : 메모장에 적혀있는 단어가 나왔는지 안나왔는지 확인만 할 수 있으면 됩니다. 중복 처리를 해주기 위해 Set 자료구조를 선언해서 해결해 주면 되겠죠? 전 Set 2개를 선언해 주었는데 가만 생각해보니 그냥 Set 하나 선언해서 remove 해주면 될 것 같습니다. //package com.example.bojtemplate; /*JAVA IO Templat..

https://www.acmicpc.net/problem/1339 1339번: 단어 수학 첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 www.acmicpc.net 해설 : 전형적인 브루트포스 문제입니다. 모든 가능한 경우의 수를 해보면 되죠. 주어진 문자열을 문자 하나씩 중복되지 않게 순차적으로 0번부터 X번이라고 가정하고 permutation을 돌려주면 됩니다. 전 중복처리를 map 자료구조를 이용해서 해주었습니다. /*JAVA IO Template Reference : 류호석*/ import javax.xml.crypto.dsig.XMLSignat..

https://www.acmicpc.net/problem/24039 24039번: 2021은 무엇이 특별할까? 백준 온라인 저지의 송년대회 Good Bye BOJ, 2021!의 개최일은 2021년 12월 31일이다. 원이는 대회가 개최된다는 사실이 기뻐 제목을 뚫어져라 보다가 2021이 무언가 특별하다는 사실을 깨달았다. 그렇 www.acmicpc.net 해설 : 단순 소수들만 뽑아주면 됩니다. sqrt(n)을 사용해서 소수 판정을 해주던가 뭐 에라토스체네스의 체를 사용해서 걸러주던가 하면 됩니다. 제한 범위가 10000밖에 안되니 절대 시간초과가 날 일은 없겠죠. #include using namespace std; using ll = long long; bool prime[10010]; void so..

https://www.acmicpc.net/problem/23563 23563번: 벽 타기 출발하자마자 오른쪽으로 한 칸 이동하고, 위로 한 칸 벽을 타고 이동하면 총 1의 시간이 소요된다. www.acmicpc.net 해설 : 루시우가 한칸 움직일때마다 1초씩 시간이 늘지만 벽을 타면 0초라는 걸 보고 일반적인 BFS 문제로는 풀기 힘들지 않을까? 라는 의문점을 가져야 합니다. 결국 이건 쉽게 생각해보면 간선의 가중치가 일정하지 않는 그래프에서 최단거리를 구하는 문제이니 그냥 다익스트라 문제입니다. 문제에서 나와있는 조건대로 코드를 작성해주면 됩니다. 벽을 타고 지나가는 부분만 조심히 잘 처리해주면 되겠군요. #include using namespace std; using ll = long long; ..

https://www.acmicpc.net/problem/14628 14628번: 입 챌린저 입력은 항상 적의 체력을 정확히 0으로 만들 수 있는 스킬의 조합만 들어온다. 첫째 줄에 스킬의 개수 N, 적의 체력 M, 같은 스킬을 사용할 때마다 추가되는 마나 포인트 K가 주어진다. (1≤N,M,K≤10 www.acmicpc.net 해설 : 문제를 이해하는건 어렵지 않습니다. 다만 점화식을 세우는 것이 너무나도 까다롭더라구요.... 여러개의 스킬을 조합해야 하고, 스킬을 사용할 수 있는 제한이 존재하지 않는 것을 통해 unbounded knapsack 문제라고 판단이 들었고 그렇게 점화식을 세웠습니다. 다만 평소에 풀어본 unbounded knapsack 문제는 1차원 배열로 해결하였는데, 1차원으로는 세워..

https://www.acmicpc.net/problem/23562 23562번: ㄷ 만들기 2021년, 냅다 ㄷ 만들기는 한국인의 기본 소양이 되었다. 우리는 앞에 놓여있는 $n \times m$ 모눈종이에 냅다 ㄷ을 그리려 한다. ㄷ 모양은 $k \times k$ 정사각형 7개를 붙인 형태로 정의한다. 다음은 www.acmicpc.net 해설 : 단순 구현문제입니다. 그냥 모오오오오오오오오오든 경우의 수를 전부 해보면 됩니다. 크기가 1인 정사각형부터 시작해서 board 보다 크기가 커질때까지 count 해줍시다. 먼저 #의 개수를 전부 세줍시다.=>black 현재 (x,y) 에서 시작해서 ㄷ 모양을 탐색해 주면서 . 이면 #으로 바꾸어 줘야하니 count 해주고, 답을 갱신할때는 (a*count) ..