말하는 컴공감자의 텃밭

2006도 초등부 문제라니.. 껄껄 점화식을 고려해 봅시다. 한번에 한 계단 또는 두 계단씩 오를 수 있지만 연속된 계단 3개는 밟을 수 없으며 마지막은 무조건 밟아야한다. 점화식은 이번에 놓을 위치에는 무조건 딛고, 그 전 경우에서 Math.max로 더 큰값을 정해주었다. 가장 높은곳인 6에 놓을때는 dp [3] + arr [5] + arr [6] 랑 dp[4] + arr[6]중 큰 값을 가져가면 되겠다. HTML 삽입 미리보기할 수 없는 소스 다만 3까지는 하드코딩 해주어 오류를 없애주었다.

치즈는 위험해..! 문제을 요약하면 1과 0이 맞닿으면 1시간 후, 1이 0이 된다. 모두 사라지는데 걸리는 시간과 사라지기 직전 시간대의 1이 몇개 있는지 출력하면 되는 문제이다. 외각에는 치즈가 없고, 하나 이상의 구멍이 존재하는데 이는 0과 맞닿은것이 아닌걸로 취급한다. 결국 치즈의 개수가 0까지 bfs()로 탐색을 지속하고, 외각에서부터 0 주변에 1이 있다면 0으로 바꾸고, 치즈 개수를 줄여주면 되겠다. 또한 한 사이클마다 치즈 개수를 저장하여 다 사라지기 직전 치즈 개수를 남겨주면 되겠다. 알고리즘 공부를 입출력이 너무 크지 않는 한 Scanner만 사용했는데 BufferedReader, StringTokenizer, BufferedWriter 을 사용해서 풀어보려 한다. 정리: https:/..

이전 문제와 비슷하다. 사실 얘를 먼저풀었는데 블로그에 정리를 안했었네~ ++ https://hb-in99.tistory.com/89 백준 7576번 토마토 G5 - BFS 요즘 지문 긴게 좋더라.. 뭔가 풀고 뿌듯한 느낌이 든다. 이해 잘못하면 큰일이긴 한데 ㅎㅎ 이 문제는 쉬운 BFS인데 시작점이 여러개라는 점과 날짜를 어떻게 기록하지? 가 관건인 문제였다. 익 hb-in99.tistory.com 이 친구도 동일하지만 이번엔 층이 생겼다. 기존에는 row와 col로만 찾았다면 이젠 위층도 생겨버렸다. 전에 해서 쉽쥬~ 실수만 하지 맙시다. 큐에 익은 토마토 모두 넣고 bfs 돌리기!! 이왕 함수로 뺀겸 범위 체크도 분리해서 가독성 올려주었다. HTML 삽입 미리보기할 수 없는 소스

요즘 지문 긴게 좋더라.. 뭔가 풀고 뿌듯한 느낌이 든다. 이해 잘못하면 큰일이긴 한데 ㅎㅎ 이 문제는 쉬운 BFS인데 시작점이 여러개라는 점과 날짜를 어떻게 기록하지? 가 관건인 문제였다. 익은 토마토 주변에 안익은 토마토가 있다면, 하루지나고 익어버린다. 다 익는 최소 날짜를 출력해야하고, 못익거나 처음부터 다 익은 경우는 각각 -1, 0을 출력하면 된다. 날짜 출력이 관건인데 이를 +1로 해결했다. 이 방법을 찾지못해서 온갖 방법을 쓰다가 결국 남의 블로그들을 뒤져보았다 호호 ㅠㅠ 익은 토마토 근처에 토마토가 있다면, 익은 토마토의 값 +1을 해주어 마지막 토마토값을 출력하면 날짜가 되었다. 로직을 자연어로 정리하면 1. 익은 토마토 1을 발견하면 Que에 넣는다. 2. Que가 빌때까지 반복한다...

코테 준비할수록 DP 점화식을 찾거나 규칙 찾는거에 약한듯해서 DP위주로 준비하게 된다. 그래프는 이제 좀 감 잡았나 싶네 껄꼴껄~ 소주 땡긴다 문제를 읽고 가능한 수를 먼저 떠올리는 습관을 들였다. 문제를 보면 한 스티커를 선택하면 상하좌우 모두 사용이 불가능하다. 따라서 연속적으로 사용할 수 없고, 지그재그로 사용하면 가장 많은 수의 스티커를 붙일 수 있다. 하나의 경우가 더있는데 이런 경우도 존재했다. 어릴적 바둑배웠는데 '날일자' 日 생각나네 그러면 점화식을 세워준다. > DP[0][3] = DP[1][0] + arr[0][3] 또는 DP[1][2] + arr[0][3] 아래 스티커 >> DP[1][3] = DP[0][0] + arr[1][3] 또는 DP[0][2] + arr[1][3] 으로 점화..

오래걸렸다. 순환되는 경우를 고려했는데 생각해보니 필요가 없었다. 단방향 간선이 주어지고, 1->2 갈수있고, 2->3, 3->1 이라면 1에서 1,2,3 모두 갈 수 있게 표기해야하는 문제다. 가보자. 플로이드 위셜은 N^3으로 음수가 없는 최단 경로의 가중치를 계산하는데 적합하다. 3중 for문을 사용하여 탐색하고, i에서 j로 갈수 있다면, i -> k , k -> j가 가능한지 판단해서 초기화 해준다. 이 문제는 가중치는 없으나 i에서는 j만 갈 수 있으나 j를 거쳐 k로 가는 방법도 알아야 하므로 사용했다. HTML 삽입 미리보기할 수 없는 소스 애를 먹었다. k i j. 순이 아닌 i j k로 작성했기 때문이다. i에서 j로 간다면 i j 와 j k가 갈 수 있는지 판단하는건 당연한데 로직을 ..

깔린 브론즈들은 다 지우고 싶다.

K번째 숫자를 지워주면 된다. 쉽지용 queue를 활용해 줍니다. HTML 삽입 미리보기할 수 없는 소스

DFS BFS 구현 문제이다. 싸피 준비하면서 가장 신경쓰는 부분인데 당연히 쉽게 풀어냈다. 유의점은 방문할수 있는 정점이 여러 개면 정점 번호가 작은것부터 먼저 방문해야한다. HTML 삽입 미리보기할 수 없는 소스 언제나 DFS 는 재귀함수, 방문한곳 true 후 다시 false로 돌려두기 기억하고 BFS는 Que를 LinkedList로 구현한 다음 add한 값에서 poll()로 조건을 넣어 계산하는걸 기억하자쟈자쟈자ㅑ

수학 구현 문제네오, 유의할 점은 숫자 배열에따라 길게 가져가는게 이득일 수도 있네오 예제 2 입력처럼 2 1 -4 3 4 -4 6 5 가 있으면 2부터 5까지 전부 더하는게 더 큰 경우가 생기듯 더했을때 생기는 이점을 고려하면서 짜면 될듯 합니다. dp를 사용해서 인덱스마다 값을 정해서 Math.max 비교로 해도 되겠네오 실수를 했었고만 꼴꼴 HTML 삽입 미리보기할 수 없는 소스