문제 링크 1744번: 수 묶기 풀이 그리디 문제 아이디어는 양수는 양수끼리 절댓값이 큰 것끼리 묶고, 음수는 음수끼리 절댓값이 큰 것끼리 묶는다. 값을 입력받으며 양수이면 plus 벡터에 넣고, 음수면 minus 벡터에 넣는다. plus는 내림차순 정렬, minus는 오름차순 정렬한다. greedy함수를 통해 각 벡터의 최댓값을 구해 더해준다. 2번 과정을 통해 각 벡터는 절댓값이 큰 순서대로 내림차순 정렬 되어 있을텐데, 처음부터 묶어주거나 묶지 않거나를 선택해준다. 선택은 현재 숫자와 다음 숫자의 곱이 합보다 클 경우에 묶어준다. 묶어줄 경우 인덱스는 +2를 해줘야 중복해서 묶지 않게 된다. 묶지 않을 경우 인덱스를 +1 해줘서 그 다음 숫자와 묶일 수 있는지 확인하도록 한다. 그렇게 구한 양수와 ..
문제 링크 5052번: 전화번호 목록 풀이 문자열 문제. 처음에는 완탐으로 했는데 시간초과가 나길래.. 찾아보았다. 정렬하는 것까진 맞았는데, 정렬을 하게 되면 바로 뒤에꺼만 확인하면 된다. 하하 문자열을 입력받고 정렬한다. 현재 문자열을 기준으로 다음 문자열을 substr로 잘라서 같은지 확인한다. 같으면 NO, 전체 확인이 끝나도 flag가 true라면 YES를 출력한다. 코드 #include #include #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int t; cin >> t; for (int i = 0; i > n; vector ..
문제 링크 1339번: 단어 수학 풀이 그리디를 사용하는 문제 처음엔 그냥 순서대로 점수 넣으려다 ACA BBD 같은 반례가 생각나서 우선순위? 느낌으로 변경함 문제를 입력받으며 가장 긴 문자열의 길이를 구해준다. maxLen 각 단어마다 알파벳의 우선순위를 구해주는데, ABC라는 단어가 있음면 A=100, B=10, C=1이 되게 구해준다. 그러면 각 알파벳마다 우선순위가 구해지는데, map으로 되어있기 때문에 vector로 바꿔주어 value기준 내림차순 정렬을 해준다. 우선순위가 높은 알파벳부터 9를 배정해주고 값을 하나씩 줄이며 숫자를 대응해준다. 다시 단어를 돌면서 대응한 숫자를 넣고 answer에 더해준다. 코드 #include #include #include #include #include ..
문제 링크 11057번: 오르막 수 풀이 DP로 푸는 문제 1자리 수일 때는 0~9까지 10개 2자리 수일 때는 00~09, 11~19 ~ 99해서 55개이다. 규칙은 n길이의 맨 첫번째 숫자가 만약 5라고 한다면 n-1길이의 숫자에서 55~99까지의 개수가 5로 시작하는 오르막 수의 개수일 것이다. 3 길이의 5로 시작하는 오르막 수를 구한다면, 555~559, 566~569, ..., 588~589, 599가 될 것이다. 해당 범위로 자른 이유는 n-1길이에서 55~59의 개수, 66~69의 개수 .. 를 구했을 것이기 때문이다. 점화식은 arr[n][i] = arr[n-1][i] + arr[n][j+1] (누적합으로 구해줄 것임) 코드 #include #include #define mod 10007..
문제 링크 9465번: 스티커 풀이 DP를 이용하는 문제 예시가 문제와 같이 다음 표라고 생각해보면 50 10 100 20 40 30 50 70 10 60 다음과 같이 생각할 수 있다. 50 10 + 30 100 + max(100, 30) = 200 20 + max(120, 100) = 140 40 + max(210, 120) = 250 30 50 + 50 70 + max(40, 50) = 120 10 + max(200, 40) = 210 60 + max(140, 200) = 260 정리하면, 해당 칸을 뜯는다고 가정할 때, 바로 대각선을 뜯을 것이냐 아니면 그 전 대각선을 뜯을 것이냐만 생각하면 된다. 점화식은 dp[0][j] = dp[0][j] + max(dp[1][j-1], dp[1][j-2]) 코..
문제 링크 11052번: 카드 구매하기 풀이 DP를 이용하는 문제 점화식을 구한다. n이 4라고 하면 4개짜리 하나 사는 경우와 `,2,3개짜리를 섞어서 사는 여러 경우가 있을 것이다. dp의 i번째 인덱스는 i개를 살 때 최댓값을 지불하는 경우가 저장되어 있을 텐데, 이를 이용해 1개짜리 사는 최댓값과 3개짜리 사는 최댓값을 더한 경우, 2개짜리 살 때 최댓값을 두 번 지불하는 경우, 그냥 4개짜리 사는 경우들에서 최댓값을 구해준다. 정리하면 점화식은, dp[n] = max(dp[1]+dp[n-1], dp[2]+dp[n-2], ... , dp[n/2]+dp[n-n/2], dp[n](입력하면서 그냥 여기에 넣어줄거임))이 될 것이다. 점화식을 이용해 코드를 짜는데, 같은 경우를 두 번 계산하지 않기 위해..
문제 링크 14940번: 쉬운 최단거리 풀이 BFS를 이용하는 문제. 반례를 잘못 처리해서 틀렸었음 3 3 2 0 0 0 0 1 0 1 1 입력을 받으며 목표지점일 경우(2일 경우)에는 dest에 넣어준다. BFS를 시작한다. 각 거리가 갱신될 벡터 dist는 -1로 초기화한다. 보통 난 0으로 초기화해주는데, 여기서 갈 수 있는 길인데 못 가는 경우를 처리하기 위해 -1로 처리한다. 상하좌우를 돌면서 범위 밖이거나 0이라면 continue한다. 각 거리를 갱신해준 뒤 q에 push한다. dist를 출력하는데, 반례와 같이 원래 못 가는 곳은 0으로 처리해야 하는데, -1로 출력될 수 있어 여기서 처리해준다. arr[i][j]가 0인데 dist[i][j]가 0이 아니라면 0으로 만들어준 뒤 출력한다. 코..
문제 링크 1238번: 파티 풀이 인접 리스트들에 대해 각 정점에서 목표 정점까지의 최단 거리를 구하는 다익스트라 문제 우선 순위 큐로 풀어야하나 싶은데 큐로 해도 풀리긴 함 값을 입력 받으며 인접 리스트를 만들어줌 func에서 현재 정점인 cur에서 각 노드까지의 최단 거리를 구해준다. 거리를 갱신해줄 dist를 무한대로 만들어주고 시작 노드는 0 큐가 빌 때까지 반복하는데, 현재 노드인 curN에서 연결된 정점을 보며 각 노드까지 거리가 최소로 갱신될 때만 dist 갱신과 q에 추가해준다. 그렇게 현재 정점에서 각 노드까지의 최소 거리가 구해진다. xdist는 집으로 각자 돌아갈 때인데, 한 번만 구해주면 각 노드까지의 최소 거리가 만들어진다. xdist[i]와 cdist[i]를 더한 값이 가장 큰 ..
문제 링크 1138번: 한 줄로 서기 풀이 answer 벡터를 0으로 초기화한다. 작은 키부터 자리를 찾아가는데, 이렇게 하게 되면 answer의 0은 자기보다 큰 키가 될 것이다.(자기 이후에 찾게 될테니) answer를 돌면서 자기보다 큰 키면(answer[j] == 0) zeroCnt를 하나 더해준다. 그렇게 zeroCnt가 arr[i]와 같아지게 되면 해당 자리의 다음 자리에 넣어주면 된다. 그 자리가 비어있지 않다면(0이 아니라면) 빈 자리를 찾아 넣어준다. answer를 출력한다. 코드 #include #include using namespace std; int main() { ios_base::sync_with_stdio(0); cin.tie(0); int n; cin >> n; vector..
문제 링크 16507번: 어두운 건 무서워 풀이 누적합 문제 사진의 밝기를 입력받으며, 각 행마다 누적합을 구한다. func를 통해 영역의 사진 밝기 평균을 구하는데, 각 행열은 1부터 시작하므로 -1 해준다. r1부터 r2까지 행마다 c2에서 c1-1의 값을 빼주면 해당 행의 영역 값을 구할 수 있다. c1이 0이라면 c1-1에서 에러가 나니까 예외 처리를 해준다. 사각형의 영역값으로 sum을 나눠주면 된다. 코드 #include #include using namespace std; int func(vector &arr, int r1, int c1, int r2, int c2) { int sum = 0; for (int i = r1; i > r >> c >> q; vector arr(r, vector(..
