이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 66 번째 글 입니다.
- Part 1 - 백준(1003번): 피보나치 함수
- Part 2 - 백준(1010번): 다리놓기
- Part 3 - 백준(1012번): 유기농 배추
- Part 4 - 백준(10159번): 저울
- Part 5 - 백준(10164번): 격자상의 경로
- Part 6 - 백준(1018번): 체스판 다시 칠하기
- Part 7 - 백준(1018번): 체스판 다시 칠하기
- Part 8 - 백준(1022번): 소용돌이 예쁘게 출력하기
- Part 9 - 백준(10775번): 공항
- Part 10 - 백준(10816번): 숫자 카드2
- Part 11 - 백준(10816번): 숫자카드 2
- Part 12 - 백준(10819번): 차이를 최대로
- Part 13 - 백준(10830번): 행렬 곱셈
- Part 14 - 백준(10844번): 쉬운 계단수
- Part 15 - 백준(10868번): 최소값
- Part 16 - 백준(1092번): 배
- Part 17 - 백준(11003번): 최솟값 찾기
- Part 18 - 백준(1102번): 발전소
- Part 19 - 백준(11048번): 이동하기
- Part 20 - 백준(11053번): 가장 긴 증가하는 부분 수열
- Part 21 - 백준(11054번): 가장 긴 바이토닉 부분 수열
- Part 22 - 백준(11055번): 가장 긴 증가하는 부분 수열2
- Part 23 - 백준(11057번): 오르막 수
- Part 24 - 백준(1120번): 문자열
- Part 25 - 백준(11403번): 경로 찾기
- Part 26 - 백준(11404번): 플루이드
- Part 27 - 백준(1149번): RGB 거리
- Part 28 - 백준(11559번): puyo puyo
- Part 29 - 백준(11655번): ROT13
- Part 30 - 백준(1167번): 트리의 지름
- Part 31 - 백준(11722번): 가장 감소하는 부분 수열
- Part 32 - 백준(12015번): 가장 긴 증가하는 부분 수열(LIS) 2
- Part 33 - 백준(12851번): 숨바꼭질2
- Part 34 - 백준(12852번): 1로 만들기 2
- Part 35 - 백준(12865번): 평범한 배낭
- Part 36 - 백준(1300번): K번째 수
- Part 37 - 백준(1325번): 효율적인 해킹
- Part 38 - 백준(13549번): 숨바꼭질3
- Part 39 - 백준(13913번): 숨바꼭질4
- Part 40 - 백준(14002번): 가장 긴 증가하는 부분 수열 4
- Part 41 - 백준(1431번): 시리얼 넘버
- Part 42 - 백준(1436번): 영화감독 숌
- Part 43 - 백준(14499번): 주사위 굴리기
- Part 44 - 백준(14888번): 연산자 끼워넣기
- Part 45 - 백준(14889번): 스타트와 링크
- Part 46 - 백준(14891번): 톱니바퀴
- Part 47 - 백준(15658번): 연산자 끼워넣기 2
- Part 48 - 백준(15686번): 치킨 배달
- Part 49 - 백준(1697번): 숨바꼭질
- Part 50 - 백준(1697번): 숨바꼭질
- Part 51 - 백준(1707번): 이분 그래프(Bipartite Graph)
- Part 52 - 백준(1708번): 볼록 껍질
- Part 53 - 백준(17136번): 색종이 붙이기
- Part 54 - 백준(1717번): 집합의 표현
- Part 55 - 백준(17298번): 오큰수
- Part 56 - 백준(17626번): Four Squares
- Part 57 - 백준(18870번): 좌표 압축
- Part 58 - 백준(1890번): 점프
- Part 59 - 백준(1918번): 후위 표기식
- Part 60 - 백준(1929번): 소수 구하기
- Part 61 - 백준(1963번): 소수 경로
- Part 62 - 백준(1965번): 상자넣기
- Part 63 - 백준(1976번): 여행가자
- Part 64 - 백준(1987번): 알파벳
- Part 65 - 백준(1992번): 쿼드트리
- Part 66 - This Post
- Part 67 - 백준(20040번): 사이클 게임
- Part 68 - 백준(2042번): 구간 합 구하기
- Part 69 - 백준(2108번): 통계학
- Part 70 - 백준(2110번): 공유기 설치
- Part 71 - 백준(2156번): 포도주 시식
- Part 72 - 백준(2193번): 이친수
- Part 73 - 백준(2231번): 분해합
- Part 74 - 백준(2250번): 트리의 높이와 너비
- Part 75 - 백준(2293번): 동전 1
- Part 76 - 백준(2294번): 동전 2
- Part 77 - 백준(2343번): 기타 레슨
- Part 78 - 백준(2468번): 안전 영역
- Part 79 - 백준(2512번): 예산
- Part 80 - 백준(2529번): 부등호
- Part 81 - 백준(2565번): 전깃줄
- Part 82 - 백준(2581번): 소수
- Part 83 - 백준(2583번): 영역구하기
- Part 84 - 백준(2630번): 색종이 만들기
- Part 85 - 백준(2644번): 촌수계산
- Part 86 - 백준(2667번): 단지번호붙이기
- Part 87 - 백준(2751번): 수 정렬하기 2
- Part 88 - 백준(2798번): 블랙잭
- Part 89 - 백준(2904번): 수학은 너무 쉬워
- Part 90 - 백준(2986번): 파스칼
- Part 91 - 백준(3015번): 오아시스 재결합
- Part 92 - 백준(3190번): 뱀
- Part 93 - 백준(3190번): 벽 부수고 이동하기
- Part 94 - 백준(4195번): 친구 네트워크
- Part 95 - 백준(4948번): 베르트랑 공준
- Part 96 - 백준(4963번): 섬의 개수
- Part 97 - 백준(4991번): 로봇 청소기
- Part 98 - 백준(5373번): 큐빙
- Part 99 - 백준(5437번): 불
- Part 100 - 백준(6171번): 땅따먹기
- Part 101 - 백준(6603번): 로또
- Part 102 - 백준(6603번): 로또
- Part 103 - 백준(7562번): 나이트의 이동
- Part 104 - 백준(7568번): 덩치
- Part 105 - 백준(7576번): 토마토
- Part 106 - 백준(7579번): 앱
- Part 107 - 백준(7785번): 회사에 있는 사람
- Part 108 - 백준(9012번): 괄호
- Part 109 - 백준(9020번): 골드바흐의 추측
- Part 110 - 백준(9184번): 신나는 함수 실행
- Part 111 - 백준(9251번): LCS
- Part 112 - 백준(9421번): 소수상근수
- Part 113 - 프로그래머스: 가장 큰 정사각형 찾기
▼ 목록 보기
실버2 : two pointer 문제이다.
풀이
- 투포인터는 i이상 j미만으로 짠다.
- 같을 경우는 i를 늘려서 파악한다. 즉 왼쪽이 더 많이 따라오는 구조
- 일단 왼쪽이 갈 수 있으면 최대한 배려해주는 느낌
- 근데 못가, 그러면 이제 오른쪽이 기준이 되어서 판단
- 어차피 i, j가 같아진다면 sum 이 0이 되어서 j를 늘릴 수 밖에 없다.
- 끝까지 j가 갔는데, 값이 M보다 크면 i를 늘려가면서 후보값이 있는지 확인해볼 수 있다.
- 하지만 끝까지 갔는데 i이상 j미만의 값이 M보다 작다면 더이상 가능성이 없으니 종료한다.
i이상 j미만이 중요하다. 그리고 마지막처리가 중요한데, 이러한 부분에 있어서 다양한 결과를 예상하고 손코딩하는 것이 중요하다는 것을 느꼈다.
지금 같은 경우 파악해볼 만한 것이, 결국 마지막에 도착했을 때, 값이 큰 경우, 같은 경우, 작은 경우에 대해 판단해보면 된다.
Code
import sys
input = sys.stdin.readline
n, m = map(int, input().split())
a = list(map(int, input().split()))
i, j, ans, bound = 0, 0, 0, 0
while True: # i이상 j미만의 bound를 확인할 것임
if bound == m: # 먼저 지금 값이 정답인지 확인
ans += 1
if bound >= m:
bound -= a[i]
i += 1
elif j == n: # 특정 i부터 j미만값까지 봤는데, j가 N이야. 즉 끝까지 간거지
break # 근데 값이 이미 M보다 작아, 그럼 할 수 있는 건 i를 늘리는 것 밖에. 근데 그건 무조건 작지
else:
bound += a[j]
j += 1
print(ans)