전체 글 (125) 썸네일형 리스트형 2251 물통 https://www.acmicpc.net/problem/2251 2251번: 물통 각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부 www.acmicpc.net 각 물통의 특징에 유의해서 보자. 모든 물통의 용량이 200이하 이고, 3개이다. 즉, 3가지 물통의 상태를 3차원 배열로 나타낼 수 있다. 이를 바탕으로 bfs를 수행하면 모든 상태를 탐색할 수 있다. 방문한 상태를 다시 탐색하지 않기 때문이다. 답을 구하는 과정은 중간에 첫 번째 물통의 용량이 0일 때 TreeSet에 넣도록 했다. 고찰: 물통의 물을 다른 물통에 옮기는 과.. 2230 수 고르기 https://www.acmicpc.net/problem/2230 2230번: 수 고르기 N개의 정수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에서 두 수를 골랐을 때(같은 수일 수도 있다), 그 차이가 M 이상이면서 제일 작은 경우를 구하는 프로그램을 작성하시오. 예를 들어 www.acmicpc.net 틀린 이유 투포인터의 범위 증감 방향을 잘못 설정. 정렬했기 때문에 인접한 원소가 가장 작은 차이를 가진다. 따라서 인접한 원소부터 범위를 늘려가면서 최적해를 찾아야 답을 찾을 수 있다. 문제 접근 N이 10만이기 때문에 완전탐색은 사용불가능. 차이가 최소인 경우를 찾기 위해 정렬이 필요하다. 차이를 비교하면서 탐색해야 하는데, 이 때 투포인터를 사용하여 인접한 원소가 가장 작.. 15565 귀여운 라이언 https://www.acmicpc.net/problem/15565 15565번: 귀여운 라이언 꿀귀 라이언 인형과, 마찬가지로 꿀귀인 어피치 인형이 N개 일렬로 놓여 있다. 라이언 인형은 1, 어피치 인형은 2로 표현하자. 라이언 인형이 K개 이상 있는 가장 작은 연속된 인형들의 집합의 www.acmicpc.net 투포인터라는 개념을 알고 있으면 쉽게 풀 수 있는 문제다. N이 10만이기 때문에 N^2의 탐색 방법을 사용하면 시간초과가 발생한다. 따라서 최대한 N에 가깝게 풀어야 한다. 이 문제에서는 범위를 최대한 넓게 탐색한 뒤에 조건을 만족한다면, 왼쪽부터 범위를 줄여가면서 최적해를 찾는다. 이 때, 범위를 1씩 줄이면서 답을 갱신하면 원하는 답을 얻을 수 있다. 정답 코드 더보기 import ja.. 이전 1 ··· 11 12 13 14 15 16 17 ··· 42 다음