전체 글 (88) 썸네일형 리스트형 백준 2477 <참외밭> 개인적으로는 실버 5?라고 느껴지지 않을 만큼 생각할 것이 많았던 문제이다. 우선 생각해 줬던 부분이 어덯게 저 부분만 빼줄 수 있는가 였다. 그렇게 해서 생각한 부분이 전체 직사각형에서 저부분을 빼주면 될 것이라 생각하고 문제를 접근했다. 문제 풀이 가로, 세로 각각 최대 길이를 구하고 그길이의 곱이 즉 빈칸 부분도 포함한 직사각형. 각각의 이전 방향을 고려해서 4가지 꺽인 부분을 고려해서 그 값을 계산해주기 직사각형의 넓이에서 꺽인 부분을 빼주기 이렇게 직사각형을 구하고 노란색 부분을 빼주는 식이 되는 것이다. 안으로 움푹 파인 부분을 구하기 위해서는 이렇게 총 4가지 경우를 생각해주면 된다. 이 경우를 고려해서 알고리즘을 짜주었다. 1번의 가장 큰 직사각형을 구하는 식이다. 이렇게 움푹파인 부분을 .. 백준 2491 <수열> 일반적으로 DP라고 생각하면 더욱 간단한 문제인 것 같다. DP라고 해서 어렵게 생각하는 것이 아닌 이전까지의 값을 저장한다는 의미에서 DP가 될 것이다. 이 문제를 단순히 브루트 포스로 접근하게 되면 n*n 값으로 시간 초과가 날 가능성이 높다. 해결방법 우선 오름차순 내림차순 두 번의 검사가 필요하다. check라는 int형 배열을 만든다 이 배열은 현재 지점까지 자신이 포함된 가장 긴 수열의 길이이다. 오름 차순일 경우는 이전 값이 자기와 같거나 작으면 이전 check 값에 1 증가 아니면 1을 입력 (내림차순은 반대) check배열을 확인해서 가장 큰 값을 result값에 넣고 출력 오름 차순 내림 차순 전체 코드 더보기 import java.io.BufferedReader; import java.. 백준 2563 <색종이> 색종이의 수가 100이하이고 흰색도화지 크기가 100이기때문에 완전탐색으로도 가능한 문제이다. 그렇지 않다면 인덱스 트리를 이용해서 풀어야하는 문제이다. 이 문제의 시간 복잡도를 계산한다면 최대 색종이의 수*도화지의 크기*색종이의 크기 이므로 100000 10만이 될것이다. 이러한 문제는 시간복잡도를 게산하면서 풀면 더욱 도움이 될것이다. 문제 해결순서 boolean형 visit 2차원 배열에 각각의 색종이 시작점으로 부터 10크기만큼 체크해준다 겹치는 부분이면 어차피 true기때문에 신경 안써줘도 됨 마지막에 전체 도화지 크기에 몇개의 true가 있는지 확인 전체 코드 더보기 import java.io.BufferedReader; import java.io.IOException; import java... 이전 1 ··· 14 15 16 17 18 19 20 ··· 30 다음
