최데브는 오늘도 프로그래밍을 한다.

#include #include #include #include #include using namespace std; int n, m; int dx[] = {-1,-1,-1,1,1,1,0,0}; int dy[] = {-1,0,1,-1,0,1,-1,1}; vector visit; string board[5]; bool findword(const string& s, int x, int y ) { //s.substr(1) 로 인해서 재귀를 한번 할때마다 첫번째 글자가 다음 글자로 바뀜 if (board[x][y] != s[0]) return false; if (s.size() == 1) return true;//비교할 글자가 한글자가 되면 탈출 for (int i = 0;i < 8;i++) {//상하좌우대각선..

dp 문제였다. 먼저 코드는 아래와 같다. #include #include #include #include using namespace std; int dp[1000001]; int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; dp[1] = 0; dp[2] = 1; dp[3] = 1; for (int i = 4;i

dp유형중 헷갈리는 유형을 정리해보려고 급하게 쓴다. 이런 유형들의 문제는 착각하기 쉬운게 가장 적게 사용하도록 만들라고 해서 조건에 해당하는것중에서 가장 큰거부터 골라나가면 가장 적게 사용하고 구해지겠지? 라고 착각하는것이다. 말이 이상한데 풀어말하자면 동전2 같은 경우에는 동전 종류 3개 이것들을 사용해서 합 15를 만드는데 동전을 가장 적게 사용할때를 구하는건데 동전 종류중에서 12원이 가장 크므로 12를 선택해버리면 남는 3원은 1원짜리 3개로 채워야하기 때문에 동전을 4개 써야하는데 이건 최소가 아니다. 5원동전 3개를 쓰면 해결되기 때문. 이런 오류를 범해서는 안된다. 아래는 제곱수의 합 코드 #include int main(void){ int N; int Dp[100001] = {}; sca..

문제 설명 네트워크란 컴퓨터 상호 간에 정보를 교환할 수 있도록 연결된 형태를 의미합니다. 예를 들어, 컴퓨터 A와 컴퓨터 B가 직접적으로 연결되어있고, 컴퓨터 B와 컴퓨터 C가 직접적으로 연결되어 있을 때 컴퓨터 A와 컴퓨터 C도 간접적으로 연결되어 정보를 교환할 수 있습니다. 따라서 컴퓨터 A, B, C는 모두 같은 네트워크 상에 있다고 할 수 있습니다. 컴퓨터의 개수 n, 연결에 대한 정보가 담긴 2차원 배열 computers가 매개변수로 주어질 때, 네트워크의 개수를 return 하도록 solution 함수를 작성하시오. 제한사항 컴퓨터의 개수 n은 1 이상 200 이하인 자연수입니다. 각 컴퓨터는 0부터 n-1인 정수로 표현합니다. i번 컴퓨터와 j번 컴퓨터가 연결되어 있으면 computers[..

문제 설명 트럭 여러 대가 강을 가로지르는 일 차선 다리를 정해진 순으로 건너려 합니다. 모든 트럭이 다리를 건너려면 최소 몇 초가 걸리는지 알아내야 합니다. 트럭은 1초에 1만큼 움직이며, 다리 길이는 bridge_length이고 다리는 무게 weight까지 견딥니다. ※ 트럭이 다리에 완전히 오르지 않은 경우, 이 트럭의 무게는 고려하지 않습니다. 예를 들어, 길이가 2이고 10kg 무게를 견디는 다리가 있습니다. 무게가 [7, 4, 5, 6]kg인 트럭이 순서대로 최단 시간 안에 다리를 건너려면 다음과 같이 건너야 합니다. 따라서, 모든 트럭이 다리를 지나려면 최소 8초가 걸립니다. solution 함수의 매개변수로 다리 길이 bridge_length, 다리가 견딜 수 있는 무게 weight, 트럭..

테스트 케이스는 통과하는데 채점에서는 시간초과 오류가 발생한다. dfs를 먼저 떠올렸는데 여기서 사용하기에는 적당한 방법이 아닌가보다. #include #include #include using namespace std; int visit[100000]; vector v; vector v3; vector v2; string temp=""; bool Standard(string A, string B) { if (A + B > B + A) return true; return false; } void dfs(vector n ,int count){ if(n.size() == count){ // 벡터 사이즈만큼 temp에 순열을 붙인 문자열을 만들게 됐을때 for(int i=0;i

문제설명 위와 같은 삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다. 삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요. 제한사항 삼각형의 높이는 1 이상 500 이하입니다. 삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다. 이 문제는 백준사이트에서도 풀어봤었다. (물론 그때는 오류가 나서 성공은 못했다.) 그래서 이번에는 맞춰버리겠다는 생각으로 풀어봤다. dp 문제였는데 거쳐간 숫자의..

문제 설명 어떤 숫자에서 k개의 수를 제거했을 때 얻을 수 있는 가장 큰 숫자를 구하려 합니다. 예를 들어, 숫자 1924에서 수 두 개를 제거하면 [19, 12, 14, 92, 94, 24] 를 만들 수 있습니다. 이 중 가장 큰 숫자는 94 입니다. 문자열 형식으로 숫자 number와 제거할 수의 개수 k가 solution 함수의 매개변수로 주어집니다. number에서 k 개의 수를 제거했을 때 만들 수 있는 수 중 가장 큰 숫자를 문자열 형태로 return 하도록 solution 함수를 완성하세요. 제한 조건 number는 1자리 이상, 1,000,000자리 이하인 숫자입니다. k는 1 이상 number의 자릿수 미만인 자연수입니다. 문제 설명과 제한 조건은 위와 같다. 입출력 예는 이렇다. 처음에..