6-6화이탱

https://www.acmicpc.net/problem/9082 9082번: 지뢰찾기 지뢰찾기 게임은 2×N 배열에 숨겨져 있는 지뢰를 찾는 게임이다. 지뢰 주위에 쓰여 있는 숫자들로 지뢰를 찾을 수 있는데, 한 블록에 쓰여진 숫자는 그 블록 주위에 지뢰가 몇 개 있는지를 나타 www.acmicpc.net 첫번째 위치, 마지막 위치, 나머지 위치 이렇게 세 구간으로 나눠서 주변 위치에 있는 지뢰 수가 모두 0이 아니라면 모두 -1 처리를 하고, 지뢰 카운트를 +1 한다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; publ..

https://www.acmicpc.net/problem/21610 21610번: 마법사 상어와 비바라기 마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기 www.acmicpc.net 처음에, 구름의 한 지점만 cloud 리스트에 넣고 풀다보니 이동할때 배열의 사이즈를 벗어나는 그런 골치 아픈 점이 생겼다,, 따라서 쉽게 구름의 4지점을 모두 리스트에 넣고 이동하는 것으로 변경했다. c.x = (n + c.x + dx[dir-1] * (len % n)) % n; c.y = (n + c.y + dy[dir-1] * (len % n)) % n; 구름 이동은 위와 같이 계산한..

https://www.acmicpc.net/problem/15685 15685번: 드래곤 커브 첫째 줄에 드래곤 커브의 개수 N(1 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에는 드래곤 커브의 정보가 주어진다. 드래곤 커브의 정보는 네 정수 x, y, d, g로 이루어져 있다. x와 y는 드래곤 커 www.acmicpc.net 처음에 이해하기 어려운 문제였다ㅠㅠ 0: x좌표가 증가하는 방향 (→) 1: y좌표가 감소하는 방향 (↑) 2: x좌표가 감소하는 방향 (←) 3: y좌표가 증가하는 방향 (↓) 백준의 예시를 보면 1세대 : → (0) 2세대 : 1세대 +1 =1 따라서, ↑ 3세대 : 2세대 +1 =2 , 1세대 +1 = 1 따라서, ← 과 ↑ 4세대 : 3세대 +1 = 3, 2세대 ..

https://www.acmicpc.net/problem/2573 2573번: 빙산 첫 줄에는 이차원 배열의 행의 개수와 열의 개수를 나타내는 두 정수 N과 M이 한 개의 빈칸을 사이에 두고 주어진다. N과 M은 3 이상 300 이하이다. 그 다음 N개의 줄에는 각 줄마다 배열의 각 행을 www.acmicpc.net dfs를 사용해여 해결할 수 있었다. 영역을 나눌때 dfs를 사용해서 연결된 빙산을 쭉 재귀로 가고 방문 표시를 한 후, 영역의 수를 올린다. 그렇게 이중 포문을 통해 방문 하지 않은 곳을 찾아 방문 한 후 영역 갯수 return ! 1년마다 높이를 깎는거는 간단하게 재귀를 사용하지 않고 3중 포문을 썼다. 이차원 배열을 하나 더 선언해서 해당 배열에 결과값을 넣고 return! import..

https://www.acmicpc.net/problem/1937 1937번: 욕심쟁이 판다 n × n의 크기의 대나무 숲이 있다. 욕심쟁이 판다는 어떤 지역에서 대나무를 먹기 시작한다. 그리고 그 곳의 대나무를 다 먹어 치우면 상, 하, 좌, 우 중 한 곳으로 이동을 한다. 그리고 또 그곳에 www.acmicpc.net 코테에서 dp문제에 치였기 때문에,, 내일까지는 dp문제만 풀거다.. ㅠㅠㅠ dfs로 풀면 시간초과가 나는 문제로, dp를 이용해야 했다! 메모이제이션을 이용해서 이전에 방문한 곳의 값을 바로 사용하게 한다. 이중포문을 사용해서 0,0부터 상하좌우를 확인한다. 대나무 수가 많은 지역이 있다면 해당 지역의 dp 값 +1 와 현재 지역의 dp값을 비교하여 더 큰 값을 dp에 넣는다. imp..

https://www.acmicpc.net/problem/2631 2631번: 줄세우기 KOI 어린이집에는 N명의 아이들이 있다. 오늘은 소풍을 가는 날이다. 선생님은 1번부터 N번까지 번호가 적혀있는 번호표를 아이들의 가슴에 붙여주었다. 선생님은 아이들을 효과적으로 보호하기 www.acmicpc.net LIS 증가하는 수열의 최대 갯수를 찾아서 n - LIS 하면 옮겨야 하는 최소값이 나온다 ! import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; public class Main { public static void main(String[] ..

https://www.acmicpc.net/problem/2579 2579번: 계단 오르기 계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. 과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점 www.acmicpc.net dp 문제로, n번째 계단의 최대 값은 1) n -1번째 계단을 밟고 n-3번째 계단을 밟은 것 , 2) n-2번째 계단을 밟은 것 이다. 예를 들어 4번째 계단의 최대값은 1) 3번째 계단과 1번째 계단 값 ㅁ ㅁ ㅁ ㅁ 2) 3번째 계단과 4번째 계단 값 ㅁ ㅁ ㅁ ㅁ 이다. import java.io.BufferedReader; import java.io.IOException; import java.io..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net dp를 사용해서 해결할 수 있었다. ㅁㅁㅁㅁ ㅁㅁㅁㅁ ㅁㅁㅁㅁ ㅁㅁㅁㅁ 이런식으로 왼쪽, 위, 왼쪽 대각선 부분을 확인하여 해당 위치들에서 가장 작은 값에 +1한 값을 넣는다. 그리고 그 값이 가장 큰 값인지 확인한다. ex) 1 1 1 0 1 1 1 0 1 1 1 0 1 1 1 1 인덱스의 시작은 (1,1) 이다! (1,1)에 1이 존재하므로, 왼쪽, 위, 왼쪽 대각선을 확인한다. -> 다 0이므로 0+1 값을 넣는다. (1,2)에 1이 존재하므로, 왼쪽, 위, 왼..

https://www.acmicpc.net/problem/11501 11501번: 주식 입력의 첫 줄에는 테스트케이스 수를 나타내는 자연수 T가 주어진다. 각 테스트케이스 별로 첫 줄에는 날의 수를 나타내는 자연수 N(2 ≤ N ≤ 1,000,000)이 주어지고, 둘째 줄에는 날 별 주가를 나타 www.acmicpc.net 오늘 코테에서 나온 유형과 비슷한 것 같아서 풀어봤는데,, 전혀 비슷하지 않았다 ㅎㅎㅎ 암튼, 이 문제는 거꾸로 포문을 돌면서 max값을 찾고, max 값보다 작을 경우에는 max값과의 차이(즉, 이익) 를 result에 넣어준다. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamR..

https://www.acmicpc.net/problem/1515 1515번: 수 이어 쓰기 세준이는 1부터 N까지 모든 수를 차례대로 공백없이 한 줄에 다 썼다. 그리고 나서, 세준이가 저녁을 먹으러 나간 사이에 다솜이는 세준이가 쓴 수에서 마음에 드는 몇 개의 숫자를 지웠다. 세준 www.acmicpc.net 실버3으로 하루를 가볍게 시작하고자 했지만,, 실버3레벨 치고 문제 이해부터 어려웠던 문제였다.. 감을 잃은건지 ㅠㅠ 너무 슬프당.. 코테 준비는 할수록 미궁으로 가는 느낌이랄까 ㅠㅠ 아무튼! 234092 을 예시로 들자면, 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 검정색인 숫자들을 다솜이가 지운거다!! 이를 확인하기 위해서는 임의의 수 i를 생..