본문 바로가기

백준33

[2457] 공주님의 정원 - C++ 날짜를 파싱하는 방법이 정말 예술이기에 글을 쓰지 않을 수 없었다. 풀이 날짜의 간격을 구해서 풀려고 했으나, 간격과는 하등 상관 없다는 것을 답을 보고 알았다. for(int i= 0; i > m1 >> d1 >> m2 >> d2; v.push_back({m1*100+d1, m2*100+d2}); } //3월 1일 = 301 //5월 28일 = 528 위와 같이 날짜를 파싱한다. 3월 1일 부터 11월 30일 까지만 꽃이 연속하여 피어 있기만 하면 된다고 한다. 계속 계속 비교해가며 가장 최소를 구해준다. 말로 설명하기 어려우니 코드로 보자 int ans = 0; int t = 301; while(t < 1201){ int nxt = t;.. 2023. 7. 9.
[2156] 포도주 시식 - C++ 몇 주 전에 답을 보고 풀었던 문제를 글을 쓰기 위해 다시 풀어 보았다. 어떻게 풀어야 할지는 기억이 나지 않는 상태에서 풀었다. 문제에 접근하는 방식 포도주잔에 들어있는 숫자들을 나열해 보았다. 조건이 있다면 3잔 연속으로 먹으면 안 된다는 것! (아래 사진 참고) 어떻게 해야 조건을 다 맞추며 해결할 수 있을까? 를 고민했다. $DP [1] = wine [1]$ $DP [2] = wine [1] + wine [2]$ 로 채워 줬는데, 그 이유는 어차피 2번째 와인을 맛보는 순서까지 왔을 때의 최대는 저것뿐이기 때문 이제 3번째부터가 문제의 문제의 문제인데, 뭐가 문제인지 살펴보자. 이렇게 되면 3잔 연속이 되어 버린다, 그렇기에 한 가지 방법이 있다. 1 번째 경우 이렇게 DP [i-2] 번째 잔까지.. 2023. 7. 2.
[2133] 타일 채우기 - C++ 2시간 정도 고민하며 여러 가지 아이디어들을 구현해 보도 결국에는 답을 보았다. 문제 1. N이 홀수 라면 타일을 채울 수 없다는 것을 알아냈다. 꾸역꾸역 채워 넣어도 한 칸이 남는 것을 알 수 있다. 2. $3\times 2$ 타일의 경우의 수 밑에 그림처럼 3가지 가능하다 N이 4일 때부터 DP를 채워 주면 될 듯싶다. 3. $3 \times 4$일 때 $$ 3 \times 3 = 9$$ 또 특수케이스를 고려해 줘야 하는데 아래처럼 2가지가 있다 직접 그려보면 알겠지만, 각 숫자에 존재하는 특수케이스는 두 개뿐이며 위 두 개 이외는 모두 중복이 됨을 알 수 있다 총 $9 + 2 = 11$가지 4. $3 \times 6$일 때 $$11 \times 3 = 33$$ 여기서부터 중복이 발생하게 되는데, 어.. 2023. 6. 29.
[3015] 오아시스 재결합 - C++ 온전히 내 힘으로 풀었다 할 수는 없지만, 첫 플레티넘 문제이고 내가 생각한 아이디어와 다른 사람의 아이디어를 적어보고 싶어 글로 작성해 본다. 아이디어 일단 규칙(?)을 찾아보려고 한다. 전 값보다 큰 게 들어온다면 전 값(2) 보다 큰 값이 들어온다면 앞의 2는 다음 사람을 보지 못하기 때문에 스택에 존재할 이유가 없어진다. 4와 같거나 큰 값, 또는 스택이 빌 때까지 POP해 준다. 전 값보다 작은 값이 들어온다면 카운트를 증가시킨다 같은 값이 들어온다면 그렇다 (2, 2), (2, 2), (2, 2), (4, 2), (4, 2), (4, 2)가 가능하다. 중복된 값을 생략하여 넣는 방법을 스택을 하나 더 만들어 구현해 봤지만 아닌 것 같아 중간에 그만뒀다. 이 부분을 대체 어떤 식으로 구현해야 할.. 2023. 6. 28.
[16236] 아기 상어 - C++ 풀이 이번 글에서는 어떻게 구상하고 설계했는지 자세하게 적어 보려고 한다 1. 나에게 가까운 것을 찾아야 한다. BFS를 사용할 수 있을 듯하다. 가까운 것이 여러 개 있다면 가장 위에 있는 것, 그중에서도 여러 개 있다면 가장 왼쪽의 것을 고르라 하니 BFS를 돌고 for문을 사용해도 될 듯하다. 시간을 표시해줘야 하니 Dist라는 -1로 채워진 $ N \times N $ 배열을 만들어 줘야 한다. 2. 상어를 성장시켜야 한다. baby라는 상어의 현재 크기를 담는 변수 growing이라는초기값은 0이고, 물고기를 먹을 때마다 증가시킨다. 만약 baby 변수와 값이 동일해진다면 baby증가, growing은 0으로 초기화 즉 상어의 무게를 늘려주는 식으로 구상했다. 3. 종료 조건 무한 반복을 돌리며 .. 2023. 6. 27.
[10942] 팰린드롬? - C++ 문제 모든 경우의 수를 확인하는 브루트 포스로 푸는 것은 불가능해 보인다. N은 최대 2000개 이고, 질문의 개수가 최대 1,000,000개 [ 1, 2000 ]이라는 질문이 1,000,000개 나온다면 20억 번 연산을 해야 하므로 0.5초 안에는 절대 불가능 Q. DP로는 가능 할까? A. 가능하다. 점화식 명령 : [ 1, 7 ]이 팰린드롬이지 확인하고 싶다면 [ 2, 6 ] 이 팰린드롬 인지 확인 하고 [ 1 ] == [ 7 ]이 같은 지 확인해 주면 된다. 그런데 또 [ 2, 6 ]이 팰린드롬인지 알려면 [ 3, 5 ]를 알아야 하므로 DP로 풀 수 있다. 테이블 정의 DP [ i ][ j ] = i번째부터 j번째 까지가 팰린드롬 인지 확인 Boolean Type 입력받기 for(int i =.. 2023. 6. 27.

티스토리툴바