티스토리 뷰

프로그래머스 2단계 주식가격 문제

 url : https://programmers.co.kr/learn/courses/30/lessons/62048?language=java


문제설명

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을 따라 1cm × 1cm의 정사각형으로 잘라 사용할 예정이었는데, 누군가가 이 종이를 대각선 꼭지점 2개를 잇는 방향으로 잘라 놓았습니다. 그러므로 현재 직사각형 종이는 크기가 같은 직각삼각형 2개로 나누어진 상태입니다. 새로운 종이를 구할 수 없는 상태이기 때문에, 이 종이에서 원래 종이의 가로, 세로 방향과 평행하게 1cm × 1cm로 잘라 사용할 수 있는 만큼만 사용하기로 하였습니다.

가로의 길이 W와 세로의 길이 H가 주어질 때, 사용할 수 있는 정사각형의 개수를 구하는 solution 함수를 완성해 주세요.


제한사항

W, H : 1억 이하의 자연수


입출력 예

 w

result 

 8

 12

80


입출력 예 설명

가로가 8, 세로가 12인 직사각형을 대각선 방향으로 자르면 총 16개 정사각형을 사용할 수 없게 됩니다. 원래 직사각형에서는 96개의 정사각형을 만들 수 있었으므로, 96 - 16 = 80 을 반환합니다.


자바코드


            
class Solution {
	public long solution(int w,int h) {
		long answer = 0;
		for(int i = 0; i < w; i++) 
			answer += (Long.valueOf(h) * i) / Long.valueOf(w);
		
		return answer * 2;
	}
}


문제설명


이 문제는 어려워 보일 수 있지만, 1차 함수 문제였다. 입출력 예제로 한다면, y = (12 / 8)x 인 함수라고 할 수 있다.

결국은 사각형에 해당 직선이 조금이라도 닿는다면 해당 사각형은 카운트할 수 없다. 1차 함수로 본다면 가로가 6번째인 사각형은 x좌표 5와 6사이에 있다!

6번째 사각형에서 x = 5 이면 y = 7.5 이다. 그러다보니 y가 7.5일때까지만 사각형을 카운트 할 수 있고 결국은 7이다. 

y = 8 일때는 직선에 걸쳐서 카운트 할 수 없다.


이번에는 가로가 3번째인 사각을 보면, x좌표가 2와 3 사이에 있다. 그리고 x = 2이면 y = 3 이다. 그러다보니 y가 3일때까지만 사각형을 카운트 할 수 있다.!

이제 규칙성이 보이는가?! 이 문제는 규칙성을 찾는 것이 어려운게 아니라 제약조건이 까다롭다.

1억이하의 자연수! 그러다보니 int로는 계산을 할 수 없다. 그렇다고 BigInteger를 사용하게 되면 속도가 느릴것이다.

그렇다면 Long! 그래서 굳이 Long으로 변환해서 알고리즘을 푼것이다.





이 문제는 정말 쉽게 풀었는데 ... 이전에 풀었던 경험이 있는 문제였다. 그때 알고리즘은 통과했었다... 그러나 1차면접에서 떨어졌다.

1차 면접은 기술면접이었는데... 왜 인성으로 떨어졌을까?! 내 인성이 그렇게 틀려먹었나? 라고 생각은 잠시도 한적없다. 사람보는 눈이 없는 것이다.

내 인성이 어때서.. 살면서 한번도 손가락질을 받아본적이 없는데!! 

댓글
댓글쓰기 폼
공지사항
Total
57,810
Today
59
Yesterday
165
TAG
more
«   2020/07   »
      1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31  
글 보관함