코디잉

https://www.acmicpc.net/problem/11659 11659번: 구간 합 구하기 4 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j www.acmicpc.net 접근 방식) 1. 배열 값 입력받을 때, 바로 누적합 배열을 생성한다. 기본 배열(arr) → 5 4 3 2 1 누적합(sum) → 0 5 9 12 14 15 sum[i] = sum[i - 1] + arr[i] 를 더해줘야 하니까, int[] sum 배열은 arr의 길이보다 하나 더 크게 만들었다. 2. 누적합을 구할 start 와 end 번호 입력받아서, 누적합 출력해준다..

https://www.acmicpc.net/problem/4796 4796번: 캠핑 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, L, P, V를 순서대로 포함하고 있다. 모든 입력 정수는 int범위이다. 마지막 줄에는 0이 3개 주어진다. www.acmicpc.net 접근 방식) "강산이는 V일 짜리 휴가를 시작했다. 캠핑장은 연속하는 P일 중, L일 동안만 사용할 수 있다." 1. 캠핑장사용날 = V / P * L (→총 휴가 일수 / 연속하는 P일 중 * L일 사용 가능) 이렇게 V / P를 하고 나면, 뒤에 남는 건 두 가지 경우가 된다. 1) L보다 작은 경우 → 작은 값 그냥 다 넣어주면 됨 (= V % P) 2) L보다 큰 경우 → L 값 넣어..

https://www.acmicpc.net/problem/10816 10816번: 숫자 카드 2 첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,0 www.acmicpc.net 일단 풀 수 있는대로 풀다가 시간초과 먼저 나서, 찾아보니 HashMap을 이용한 풀이도 있었지만 일단 이분 탐색을 공부하고 있어서 이분 탐색 사용해서 풀고 싶었다. 중복 원소의 개수를 알아내기 위해, 중복 원소의 왼쪽 끝 index과 오른쪽 끝 index을 알아내야 한다. lower bound랑 upper bound 개념에 대해 먼저 알아둬야 한다고 해서, 블..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 접근 방식) 오름차순으로 주어지는 동전을 배열에 담아서, 배열의 마지막부터 반복문을 돈다. 만들고 싶은 금액(K)과 비교해서 배열의 돈이 더 크면 continue 아니라면 K를 배열의 돈으로 나눠서 몫은 동전 개수에 더한다. (→ count += K / money[i]) 그리고 K를 나머지로 update 시켜준다. (→ K %= mo..

https://www.acmicpc.net/problem/14940 14940번: 쉬운 최단거리 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000) 다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이 www.acmicpc.net 접근 방식) 처음에 문제 쓱 읽고, 목표지점이 (0,0)에 고정된 건 줄 알았는데 아니었다. 그래서 2차원 map배열에 값을 넣어주면서, 값이 2인 목표지점의 좌표 값을 저장해뒀다. 그리고 거기서 BFS를 시작 가로,세로만 갈 수 있다니까 똑같이 동서남북 4방향으로 움직이면서, 범위 안에 있는 값이라면 거리를 1 증가시켜준다. 다 끝나고, 문제의 "원래..

https://www.acmicpc.net/problem/16918 16918번: 봄버맨 첫째 줄에 R, C, N (1 ≤ R, C, N ≤ 200)이 주어진다. 둘째 줄부터 R개의 줄에 격자판의 초기 상태가 주어진다. 빈 칸은 '.'로, 폭탄은 'O'로 주어진다. www.acmicpc.net 접근 방식) 홀수 초: 폭탄 새로 설치 + 기존 폭탄 시간-1 짝수 초: 폭탄 터짐 + 기존 폭탄 시간-1 이렇게 반복된다. **폭탄이 터질 때, 본인 + 4방향이 터지는데 여기서 나중에 터져야되는 폭탄을 미리 터뜨려버리면, 그 폭탄의 4방향은 터뜨릴 기회를 놓쳐버린다.... 이 부분을 놓쳐서 때문에 오래걸렸다 ㅠvㅠ ㅎㅎ 나는 폭탄이 1초면 터지는 걸로 설정해놨기 때문에, 폭탄을 4방향 터뜨리면서, 만약 현재 폭..

https://www.acmicpc.net/problem/2667 2667번: 단지번호붙이기 과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여 www.acmicpc.net 접근 방식) BFS 실행 횟수 → 단지 수 BFS 내에서 조건에 부합해서 queue에 add된 횟수 → 단지 내 가구 수 package tony_git.graph_traversal; import java.io.*; import java.util.*; public class B_2667 { static int N; static int[][] map; static boolean[][] visited; ..

https://www.acmicpc.net/problem/2178 2178번: 미로 탐색 첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다. www.acmicpc.net 접근 방식) 목표 노드까지의 최단 경로를 구하는 거니까 BFS 사용 기존에 방문을 나타내던 boolean[][] visited 배열 대신에, 방문하면 +1 해주며 거리를 증가시키기 위해 int[][] distance 배열을 생성한다. 그리고 상하좌우 움직이면서 x, y좌표 범위가 벗어나지 않고, 미로숫자가 1이고, 이미 방문한 곳이 아니라면 queue에 추가해준다. 다 끝났으면, distance 배열의 (N, M)에는 이동거리가..

https://www.acmicpc.net/problem/1325

https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 수라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타워 www.acmicpc.net 접근 방식) while문으로 숫자 쭉 돌면서 String.valueOf()로 문자열로 바꿔서 contains("666")으로 666포함하고 있으면 count증가시켜주면 된다. 그렇게 N번째를 찾으면 된다. package codingTestStudy.week2; import java.io.*; public class B_1436 { public static void main(String[] arg..