맞는데 왜 틀림

Prefix Sum - 2725

문제 설명입력으로 테스트 케이스 C가 주어진다.C의 갯수만큼 자연수 N이 주어진다.각 테스트 케이스마다 0,0에서 보이는 점의 갯수를 출력한다.문제 풀이사용하는 알고리즘 설명이 문제는 누적합(Prefix Sum)의 개념과 동적 프로그래밍(Dynamic Programming)의 개념이 같이 들어가있는 문제이다.보통 누적합과 동적 프로그래밍은 같이 사용하는 경우가 많다고 한다. 이전 DP 문제들에서 i번째 값은 i-1번째 값과 i번째 값 중 최대값 이런식으로 작은 것부터 계산해서 올라온 것을 기억할 것이다.이 방식이 누적합 방식이다. 예시이 문제도 예를 들어 설명하겠다.2,2를 구하려면1,1의 점의 수는 3이다.1,2의 점의 수는 4이다.2,1의 점의 수는 4이다.그렇다면 2,2의 점의 수는 1,2의 점의 ..

문제 설명테스트 케이스 T가 주어진다.테스트 케이스별로 가로 세로의 블럭 수를 C와 R로 주어진다.C*R의 갯수만큼 블럭이 각각 칸에 몇 개가 쌓여있는지 주어진다.블럭에 가려지지 않은 보이는 면을 모두 구하여 출력한다.주의사항블럭에 가려진 면만 뺀다.다시 말해서 바닥면은 가려진 것으로 치지 않는다.문제 풀이가로 세로의 갯수만큼 입력을 받은 후 블럭끼리 가려진 면을 빼는 문제이다.기하학에 구현의 알고리즘으로 바로 구현하였다. 우선 위 예시 입력을 통해 설명해보겠다.423121010001여기서 1,1 인덱스인 1의 경우를 살펴보겠다우선 1개의 블럭이므로 총 면의 수는 1*4 + 2로 총 6면을 가지고 있다. 그리고 이웃 면들을 검사해보자.이웃면이 0,1 인덱스의 2개 블럭, 1,0 인덱스의 2개 블럭이 존재..

문제 설명총 등산 거리 L, 휴식 지점 갯수 N, 1m 가는데 존이 걸리는 시간 rF, 1m 가는데 베시가 걸리는 시간 rB가 주어진다.다음 줄부터 각 휴식지점의 거리 xi와 풀의 맛 ci가 주어진다.최대로 얻을 수 있는 풀의 맛을 출력한다.조건존에게 추월당하면 안된다.문제 풀이그리디 알고리즘(Greedy Algorithm)으로 푸는 문제이다.그리디 알고리즘(Greedy Algorithm)이란?각 단계에서 그 순간에 최적이라고 생각되는 선택을 반복하여 최종적인 해답에 도달하는 알고리즘 설계 기법이다.탐욕 알고리즘으로도 불린다. 따라서 각 단계에서 최적의 선택을 할 것인데, 여기서는 뒤에서부터 탐색을 하였다.문제의 예제 입력과 출력으로 설명을 해보겠다. 입력10 2 4 37 28 1출력15 최대 맛을 가지..

문제 설명횟수가 주어진다.문자열이 주어진다.횟수만큼 문자열이 섞인다.섞이는 규칙은 K번째 글자는 K+1번째 글자 사이로 이동한다.문제 풀이이번엔 그냥 구현하는 문제이다.규칙을 우선 찾아보자.섞는 규칙을 복원하는 규칙을 찾는 것이다. 짝수 길이의 문자열의 예시우선 문제에서 순환 주기와 순환 문자열을 준다.abcdef, afbecd, adfcbe, aedbfc, acefdb순서로 순환한다.그렇다면 1번 깜빡거린걸 찾을 때 afbecd가 다시 abcdef가 되게하는 규칙을 찾아보자. 우선 순환 문자열을 보면 맨 첫 문자를 변하지 않는 것을 볼 수 있다.따라서 반복문에서 첫번째 문자열은 제외해도 된다. 이후 afbecd에서 f를 끝으로 이동시키자.1번 인덱스를 5번 인덱스로 이동시킨것이다.그러면 abecdf가 ..

저번과 이어서 DP 문제를 연습하기 위해 가져왔다.이번에는 AI의 도움 없이 혼자 풀이하였다.문제 설명미로의 크기인 1차원 배열의 크기 N과 미로의 정보인 Ai가 주어진다.미로의 정보에는 이동할 수 있는 칸의 수가 쓰여져있다.N번째 칸으로 갈 때 최소 점프 수를 구하여라.문제 풀이문제를 보자마자 저번 포스트에서 다룬 11053 문제의 접근법이 떠올랐다.같은 DP문제로 점화식을 통해 작은 문제서부터 큰 문제를 해결해나가는 방식을 똑같이 사용해보겠다.for i for j if (i-j)(두 칸 사이의 거리) result[i] = Min(result[i], result[j] + 1)(i가 최종 목적지일 경우 최소 이동 거리)여기서 Min으로 작은 값을 찾기 위해서는 result를 0으로 초기화 하면 안되고 예..

문제 설명첫째 줄에 수열 크기 A 입력둘째 줄에 수열 입력수열에서의 증가하는 부분이 가장 긴 부분의 길이를 출력문제 풀이처음에는 DP라서 점화식을 구해서 재귀로 푸는 문제로 이해했다.따라서 최대값과 그 이전의 값(최대값보다 작은 최대값)을 저장해서 인접 행렬을 순차적으로 탐색하였다.이 방법은 자기보다 작은 수를 만났을 때 초기화해서 다시 탐색해서 비교해야 하는 부분에서 잘못된 방법이라는 것을 느꼈다. AI한테 도움을 받아 접근 방식에 대한 아이디어를 받은 부분은 다음과 같이 접근하였다.수열을 제일 작은 수열에서부터 하나씩 크기를 키워 증가하는 부분이 가장 길 때의 길이를 비교하는 방식이다.예를 들면 아래와 같다.예시 입력값610 20 10 30 20 50위와 같이 입력을 받은 경우A1 = [10]A2 =..

Timer.2 - Using a timer asynchronously위 링크에 있는 Boost의 튜토리얼을 따라하며 공부해보는 글이다. 비동기 타이머를 쓰는 주제이다. Timer.2 - Using a timer asynchronouslyThis tutorial program demonstrates how to use asio's asynchronous functionality by modifying the program from tutorial Timer.1 to perform an asynchronous wait on the timer. #include #include Using asio's asynchronous functionality means supplying a completwww.boost...

문제 설명입력 첫번째 줄로 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시 번호 X가 주어짐두번째 줄부터 M개의 줄로 A B의 형태로 A->B로 가는 간선 정보가 주어짐X로부터 최단 거리가 K인 모든 도시의 번호를 오름차순으로 출력, 없는 경우 -1 출력문제 풀이이전과 동일하게 bfs 알고리즘의 문제이다. 따라서 Queue 자료형과 방문기록을 위한 코드를 사용했다. 아래는 최종 코드다.더보기using System;using System.Collections.Generic;using System.Linq;namespace StudyCS{ class Program { public class Vertex { public Vertex() ..

Timer.1 - Using a timer synchronously위 링크에 있는 Boost의 튜토리얼을 따라하며 공부해보는 글이다. 동기화 타이머 써보기가 주제이다. Timer.1 - Using a timer synchronouslyThis tutorial program introduces asio by showing how to perform a blocking wait on a timer. We start by including the necessary header files. All of the asio classes can be used by simply including the "asio.hpp" header file. #include #include All programswww.boost.o..

문제 설명가로 N, 세로 M이 주어진다.시작점은 좌측 상단도착점은 우측 하단이동은 우측과 하단만 가능시작점이 도착점일 수 있음문제 풀이1이 문제는 BFS, DFS, DP로 풀 수 있는 문제로 분류되어 있다.우선 익숙한 DFS로 풀이를 해보았다.아래는 코드다.더보기using System;using System.Collections.Generic;namespace StudyCS{ class Program { public struct Location { public Location() { x = 0; y = 0; } public int x; ..