Loading...

[swexpert] 7510. 상원이의 연속합 (c++, 누적합)

n이 최고 10^6이므로 n^2은 시간초과로 O(n)으로 풀어줘야 되는 문제이다. n=15일 때 1, 2, 3, ... ,15 를 하나씩 더하면 누적합은 1, 3, 6, 10, ... 이렇게 될 것이다. 6인 경우 1~6까지 누적합이 21이되어 15를 넘게 되면 앞에서부터 하나씩 빼준다 (연속합을 구하니깐) 21에서 1을 빼변 20, 2를 빼면 18, 3을 빼면 15가 되어 4+5+6=15 인 또 하나의 경우를 구할 수 있다. 그러니 시작이 어디부터 인지 나타내는 변수 s를 만들고 누적합이 15를 넘을 때마다 시작점을 1씩 증가시키면 된다. #define _CRT_SECURE_NO_WARNINGS #include using namespace std; int main(int argc, char** argv..

[SWEXPERT] 1232. 사칙연산 (이진트리, C++, D4)

사칙연산 유효성 검사 풀고 풀었다가 완전 이진트리로 착각하여 입력을 이상하게 받아 5번 예제부터 자꾸 틀렸다. ㅠㅠ 아닌 걸 알고 입력부분 고쳐서 해결함. 연산자를 가지는 노드는 자식이 없고 연산자인 노드만 자식을 추가적으로 입력받는다. 나머지는 재귀로 중위 계산해준다. #define _CRT_SECURE_NO_DEPRECATE #include #include #include using namespace std; double tree[1001][2]; string oper[1001]; double inorder(int num) { if (tree[num][0]) {//자식있음 double a = inorder(tree[num][0]); //왼쪽 계산 double b = inorder(tree[num][1..

[swexpert] 1244. 최대 상금 (완전탐색, C++)

최대 6자리 숫자의 자리수 중에 2개를 고르는 것: 6C2 =15가지 최대 10번 자리 교환한다 15의 10승=> 시간초과 따라서 VISIT방문 처리를 해주거나 다른 방법으로 풀어야되는데 다른 사람걸 보고 VISIT[만든숫자][교환횟수]=TRUE 이런식으로 해주면 된다. 백준의 토마토 3차원문제가 이런식으로 했던거 같은데 가끔 잊을만하면 나온다 #include #include #include #include using namespace std; int result; bool visit[1000000][11]; int toNumber(string s){ int temp=0; for(int i=0;iresult)result=temp; return; } for(int i=0;it; for(int tc=1;tc..

[swexpert] 1868. 파핑파핑 지뢰찾기 (java)

1. 먼저 numbering함수에서 폭탄이 아닌 곳의 숫자를 쓴다. (for문으로 사방돌며 폭탄 몇개인지 체크, bfs필요없음) 2. 0인 곳의 처리 (bfs) 0인 곳은 연속으로 터지므로 큐에 0을 넣고 돌려 폭탄이 아닌 곳을 모두 폭탄(-1)로 바꿔준다. -1로 바꿔주는 것은 방문표시임과 동시에 더이상 터트릴 필요가 없어지는 숫자라고 생각하면 된다. 0의 개수만큼 cnt를 1증가시켜준다. 3. 1이상 숫자인 곳의 처리 마지막 배열 이중 포문을 돌면서 1이상의 숫자들은 일일히 눌러줘야하므로 만날때마다 cnt를 1증가시켜준다. import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Sc..

[SWEA] 5604. 구간합 (java, 수학)

풀이 참고 mygumi.tistory.com/180 package algo0421; import java.util.Scanner; public class S_5604_구간합_Solution { static long t,a,b; static long[] count; static long point; public static void main(String[] args) { Scanner sc=new Scanner(System.in); count=new long[10]; point=1;//초기화 a=1; b=sc.nextLong(); while(a

[swexpert] 1247. 최적 경로 (TSP, 외판원순환 문제, JAVA)

swexpertacademy.com/main/solvingProblem/solvingProblem.do SW Expert Academy SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요! swexpertacademy.com 모든 곳을 방문하는 여러 경로 중 가장 짧은 거리를 구하는 문제 이 문제는 시간 초과를 내지는 않는 문제 같아서 그냥 DFS 돌리면 되는데 visit배열 대신 비트마스크를 썼다. import java.util.ArrayList; import java.util.Scanner; public class Solution { static int n,t; static ArrayList pos; static Integer[] home; static int dis=Intege..