👩🏻💻 문제링크 https://www.acmicpc.net/problem/1107 1107번: 리모컨 첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼 www.acmicpc.net ✍️ 아이디어 (처음에 잘못 접근함) 1. 문제 이해 처음엔 사용할수 있는 버튼을 가지고 모든 수의 조합을 만들려고 했는데 브루트포스는 그냥 모든 수(0~1000000)을 다 해보면 되는거였다 2. 0~1000000의 수를 다 해보면서.. 1. 이 채널에 고장난 버튼이 없는지 2. 누를수 있다면 목표 버튼이랑 최소차이가 나는지 확인 3. 고장난 버튼을 체크할때 2..
전체 글
👩🏻💻 문제링크 https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 e는 16진수 s는 29진수 m은 20진수 일때 10진수로 e=s=m이 되는 최소값을 구해보자 2. 내가 문제를 풀때는 가장 작은 수에 진수의 수만큼 더하고 가장 작은 수가 2개일 경우 두 수의 진수의 수만큼 더했다 3. 다른사람이 푼 방식은 년도를 하나씩 더하여 year = e+15x임을 이용해 (year-e)%15 == 0 을 조건으로 걸어서 year..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/3085 3085번: 사탕 게임 예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 문제를 처음에 이해하지 못해서 그냥 강의를 들었다 문제는 n x n 크기에 여러 색의 사탕을 놓고 인접한 곳의 사탕의 색이 다르면 둘을 바꿔서 전체에서 사탕 색이 몇개나 연속되는지 구한다 2. 배열에서 최대 몇개까지 연속되는지 찾게 해주는 함수를 만듬 3. 로직 사탕 색이 가로로or세로로 다른 사탕들을 바꾼다 사탕이 같은 색깔로 최대 몇개까지 연속으로 나오는지 구한다 바꿨던 사탕들을 원위치 시킨다 ✍️소스코드 구현하는데에 애먹음 #include #include #in..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 RGB 거리 1과 비슷해 보이지만 마지막 집이 첫번째 집과 이웃한다는 점이 다르다 가장 싸게 모든 집을 페인트칠 하는 알고리즘 근데 인접한 집은 다른 색으로 페인트칠 해야함 앞집이 빨초파 인 경우로 나눠야함 앞집이 빨간색이면 다음집은 초록과 파란집중에 작은것을 골라야함 2. 난 처음에 백트래킹 처럼 어떤 집을 선택하였는지..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net ✍️ 아이디어 1. 문제 이해 저점에서 올라갔다가 최고점 찍고 내려오는 최대 긴 수열의 항의 갯수를 구하는것임 (∧ 이런 크기로 수열이 정렬되어야함) 2. 나는 2차원 배열을 이용하여 배열의 한 요소가 내려가는 중인 경우와 올라가는 중인 경우를 나눠서 1) 올라가는 중인 경우 : 자신 보다 작은 수랑만 비교 할수 있음 2) 내려가는 중인 경우 : 자신보다 작고 큰수 둘다 비교 할수 있음 ✍️소스코드..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2156 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 포도주 n개가 일렬로 정렬되어 있고 각 잔에 들어있는 포도주의 양을 입력받을때 포도주를 가장 많이 먹을때 얼마나 먹는가 조건 : 인접한 포도주 3잔을 연속으로 들이키면 안됨 2. 나는 조건을 2개로 생각해 3차원 배열을 만듬 (2번째는 바로 전 포도주를 마신여부, 3번째는 전전 포도주를 마신 여부) 3. 생각보다 케이스가 복잡함 첫 잔을 안마시는 경우..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/9465 9465번: 스티커 첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의 www.acmicpc.net ✍️ 아이디어 1. 문제 이해 동물원과 비슷한 문제임 스티커를 뜯는데 인접한 곳의 스티커는 못씀 2. D[N][2] = 2행 N열의 스티커로 얻을수 있는 최대 정수 (0인경우 위에 스티커 사용, 1인경우 아래 스티커 사용, 2인경우 N열 스티커 사용 안함) 3. 처음에 스티커 사용 안하는것에 구현을 애먹었는데 그냥 이전 result에서 max 구하면 되는거였음 4. 나..
👩🏻💻 문제링크 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net ✍️ 아이디어 1. 문제 이해 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수를 구하자 2. 점화식 D[N][K] = 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수 3. ex) 6까지 정수 4개를 더해서 합이 6 = 6까지 정수 3개를 더해서 + 5까지 정수 3개를 더해서 + 4까지 정수 3개를 더해서 .....+ 0까지 정수 3개를 더해서 (이 아이디어는 내가 직접 떠올림 !) 4. 처음에 n=0, k=0~200 의 값이 1이라는 점을 간과함 ✍️소스코드 내 코드 #incl..